----------------------siwuxie095
索引从 0 开始
程序 1：最小索引堆的实现
MinIndexHeap.h：
#ifndef MININDEXHEAP_H
#define MININDEXHEAP_H
#include <iostream>
#include <string>
#include <cassert>
#include <algorithm>
using namespace std;
//最小索引堆：索引从0开始
template<typename Item>
class MinIndexHeap
{
private:
Item *data; //指向存储元素的数组
int *indexes; //指向存储索引的数组
int count;
int capacity;
//私有函数，用户不能调用
void shiftUp(int k)
{
//如果新添加的元素小于父节点的元素，则进行交换
while (k > 0 && data[indexes[(k - 1) / 2]] > data[indexes[k]])
{
swap(indexes[(k - 1) / 2], indexes[k]);
k = (k - 1) / 2;
}
}
//也是私有函数，用户不能调用
void shiftDown(int k)
{
//只要当前节点有孩子就进行循环
while (2 * k + 1 < count)
{
// 在此轮循环中,data[indexes[k]]和data[indexes[j]]交换位置
int j = 2 * k + 1;
// data[indexes[j]]是data[indexes[j]]和data[indexes[j+1]]中的最小值
if (j + 1 < count && data[indexes[j + 1]] < data[indexes[j]])
{
j += 1;
}
if (data[indexes[k]] <= data[indexes[j]])
{
break;
}
swap(indexes[k], indexes[j]);
k = j;
}
}
public:
MinIndexHeap(int capacity)
{
data = new Item[capacity];
indexes = newint[capacity];
//计数器，这里索引等于计数器减一
count = 0;
this->capacity = capacity;
}
~MinIndexHeap()
{
delete []data;
delete []indexes;
}
int size()
{
return count;
}
bool isEmpty()
{
return count == 0;
}
void insert(int i, Item item)
{
//防止越界
assert(count <= capacity);
assert(i >= 0 && i <= capacity);
data[i] = item;
indexes[count] = i;
count++;
shiftUp(count - 1);
}
//取出最小的data
Item extractMin()
{
//首先要保证堆不为空
assert(count > 0);
Item ret = data[indexes[0]];
swap(indexes[0], indexes[count - 1]);
count--;
shiftDown(0);
return ret;
}
//取出最小的data对应的index
int extractMinIndex()
{
assert(count > 0);
int ret = indexes[0];
swap(indexes[0], indexes[count - 1]);
count--;
shiftDown(0);
return ret;
}
Item getMin()
{
assert(count > 0);
return data[indexes[0]];
}
int getMinIndex()
{
assert(count > 0);
return indexes[0];
}
Item getItem(int i)
{
return data[i];
}
//修改 index 对应的 data
void change(int i, Item newItem)
{
data[i] = newItem;
// 找到indexes[j] = i, j表示data[i]在堆中的位置
// 之后尝试着shiftUp(j)一下, 再shiftDown(j)一下
//即看看能不能向上或向下移动以保持堆的性质
for (int j = 0; j < count; j++)
{
if (indexes[j] == i)
{
shiftUp(j);
shiftDown(j);
return;
}
}
//该函数的时间复杂度O(n)+O(lgn)级别的，也就是O(n)级别的函数
//其中：遍历是n，Shift Up和Shift Down是lgn
//
//之前的插入操作和删除操作，都能保证是lgn级别的，使得它的性
//能优势非常明显，现在修改一个元素，它的时间复杂度变成了O(n)
//级别，那么对用户来讲，在外部进行n个堆操作，在最坏的情况下，
//总的时间就有可能变成O(n^2)这个级别，这是非常不理想的一种情
//况，change()这个函数可以进行优化
}
public:
//在控制台打印测试用例
void testPrint()
{
//限制：只能打印100个元素以内的堆，因为控制台一行的字符数量有限
if (size() >= 100)
{
cout << "Fancy print can only work for less than 100 int";
return;
}
//限制：只能打印类型是int的堆
if (typeid(Item) != typeid(int))
{
cout << "Fancy print can only work for int item";
return;
}
cout << "The Heap size is: " << size() << endl;
cout << "data in heap: ";
for (int i = 0; i < size(); i++)
{
cout << data[i] << " ";
}
cout << endl;
cout << endl;
int n = size();
int max_level = 0;
int number_per_level = 1;
while (n > 0)
{
max_level += 1;
n -= number_per_level;
number_per_level *= 2;
}
int max_level_number = int(pow(2, max_level - 1));
int cur_tree_max_level_number = max_level_number;
int index = 0;
for (int level = 0; level < max_level; level++)
{
string line1 = string(max_level_number * 3 - 1, ' ');
int cur_level_number = min(count - int(pow(2, level)) + 1,
int(pow(2, level)));
bool isLeft = true;
for (int index_cur_level = 0; index_cur_level < cur_level_number;
index++, index_cur_level++)
{
putNumberInLine(indexes[index], line1, index_cur_level,
cur_tree_max_level_number * 3 - 1, isLeft);
isLeft = !isLeft;
}
cout << line1 << endl;
if (level == max_level - 1)
{
break;
}
string line2 = string(max_level_number * 3 - 1, ' ');
for (int index_cur_level = 0; index_cur_level < cur_level_number;
index_cur_level++)
{
putBranchInLine(line2, index_cur_level, cur_tree_max_level_number * 3 - 1);
}
cout << line2 << endl;
cur_tree_max_level_number /= 2;
}
}
private:
void putNumberInLine(int num, string &line, int index_cur_level,
int cur_tree_width, bool isLeft)
{
int sub_tree_width = (cur_tree_width - 1) / 2;
int offset = index_cur_level * (cur_tree_width + 1) + sub_tree_width;
assert(offset + 1 < line.size());
if (num >= 10)
{
line[offset + 0] = '0' + num / 10;
line[offset + 1] = '0' + num % 10;
}
else
{
if (isLeft)
line[offset + 0] = '0' + num;
else
line[offset + 1] = '0' + num;
}
}
void putBranchInLine(string &line, int index_cur_level, int cur_tree_width)
{
int sub_tree_width = (cur_tree_width - 1) / 2;
int sub_sub_tree_width = (sub_tree_width - 1) / 2;
int offset_left = index_cur_level * (cur_tree_width + 1) + sub_sub_tree_width;
assert(offset_left + 1 < line.size());
int offset_right = index_cur_level * (cur_tree_width + 1) + sub_tree_width
+ 1 + sub_sub_tree_width;
assert(offset_right < line.size());
line[offset_left + 1] = '/';
line[offset_right + 0] = '\\';
}
};
#endif
main.cpp：
#include"MinIndexHeap.h"
#include <ctime>
int main()
{
MinIndexHeap<int> minIndexHeap = MinIndexHeap<int>(100);
srand(time(NULL));
for (int i = 0; i < 15; i++)
{
minIndexHeap.insert(i, rand() % 100);
}
minIndexHeap.testPrint();
cout << endl;
while (!minIndexHeap.isEmpty())
{
cout << minIndexHeap.extractMin() << " ";
}
cout << endl;
system("pause");
return0;
}
运行一览：
程序 2：最小索引堆的优化
MinIndexHeap.h：
#ifndef MININDEXHEAP_H
#define MININDEXHEAP_H
#include <iostream>
#include <string>
#include <cassert>
#include <algorithm>
using namespace std;
//最小索引堆：索引从0开始
template<typename Item>
class MinIndexHeap
{
private:
Item *data; //指向存储元素的数组
int *indexes; //指向存储索引的数组
int *reverse; //指向存储反向索引的数组
int count;
int capacity;
//私有函数，用户不能调用
void shiftUp(int k)
{
//如果新添加的元素小于父节点的元素，则进行交换
while (k > 0 && data[indexes[(k - 1) / 2]] > data[indexes[k]])
{
swap(indexes[(k - 1) / 2], indexes[k]);
reverse[indexes[(k - 1) / 2]] = (k - 1) / 2;
reverse[indexes[k]] = k;
k = (k - 1) / 2;
}
}
//也是私有函数，用户不能调用
void shiftDown(int k)
{
//只要当前节点有孩子就进行循环
while (2 * k + 1 < count)
{
// 在此轮循环中,data[indexes[k]]和data[indexes[j]]交换位置
int j = 2 * k + 1;
// data[indexes[j]]是data[indexes[j]]和data[indexes[j+1]]中的最小值
if (j + 1 < count && data[indexes[j + 1]] < data[indexes[j]])
{
j += 1;
}
if (data[indexes[k]] <= data[indexes[j]])
{
break;
}
swap(indexes[k], indexes[j]);
reverse[indexes[k]] = k;
reverse[indexes[j]] = j;
k = j;
}
}
public:
MinIndexHeap(int capacity)
{
data = new Item[capacity];
indexes = newint[capacity];
reverse = newint[capacity];
//初始化reverse数组
for (int i = 0; i < capacity; i++)
{
reverse[i] = -1;
}
//计数器，这里索引等于计数器减一
count = 0;
this->capacity = capacity;
}
~MinIndexHeap()
{
delete []data;
delete []indexes;
delete []reverse;
}
int size()
{
return count;
}
bool isEmpty()
{
return count == 0;
}
void insert(int i, Item item)
{
//防止越界
assert(count <= capacity);
assert(i >= 0 && i <= capacity);
data[i] = item;
indexes[count] = i;
reverse[i] = count;
count++;
shiftUp(count - 1);
}
//取出最小的data
Item extractMin()
{
//首先要保证堆不为空
assert(count > 0);
Item ret = data[indexes[0]];
swap(indexes[0], indexes[count - 1]);
reverse[indexes[count - 1]] = -1;
reverse[indexes[0]] = 0;
count--;
shiftDown(0);
return ret;
}
//取出最小的data对应的index
int extractMinIndex()
{
assert(count > 0);
//对于外部来说，索引从0开始，所以要减一
int ret = indexes[0];
swap(indexes[0], indexes[count - 1]);
reverse[indexes[count - 1]] = -1;
reverse[indexes[0]] = 0;
count--;
shiftDown(0);
return ret;
}
Item getMin()
{
assert(count > 0);
return data[indexes[0]];
}
int getMinIndex()
{
assert(count > 0);
return indexes[0];
}
bool contain(int i){
assert(i >= 0 && i <= capacity);
//reverse数组在构造函数中都初始化为-1，
//所以拿-1做比较
return reverse[i] != -1;
}
Item getItem(int i)
{
assert(contain(i));
//对于外部来说，索引从0开始，
//对于内部来说，索引从1开始，
//所以要加一
return data[i];
}
//修改 index 对应的 data
void change(int i, Item newItem)
{
//防止越界和检查i是否在堆中，
//因为有可能已经取出去了
assert(contain(i));
data[i] = newItem;
// 找到indexes[j] = i, j表示data[i]在堆中的位置
// 之后尝试着shiftUp(j)一下, 再shiftDown(j)一下
//即看看能不能向上或向下移动以保持堆的性质
int j = reverse[i];
shiftUp(j);
shiftDown(j);
//先用O(1)的时间找到位置，再用O(lgn)的时间完成
//Shift Up和Shift Down，此时，该函数的时间复杂
//度就是O(lgn)级别的，如果有n个堆操作，总时间
//就是O(n*lgn)
//
//加入了反向查找后，性能得到了巨大的提升
}
public:
//在控制台打印测试用例
void testPrint()
{
//限制：只能打印100个元素以内的堆，因为控制台一行的字符数量有限
if (size() >= 100)
{
cout << "Fancy print can only work for less than 100 int";
return;
}
//限制：只能打印类型是int的堆
if (typeid(Item) != typeid(int))
{
cout << "Fancy print can only work for int item";
return;
}
cout << "The Heap size is: " << size() << endl;
cout << "data in heap: ";
for (int i = 0; i < size(); i++)
{
cout << data[i] << " ";
}
cout << endl;
cout << endl;
int n = size();
int max_level = 0;
int number_per_level = 1;
while (n > 0)
{
max_level += 1;
n -= number_per_level;
number_per_level *= 2;
}
int max_level_number = int(pow(2, max_level - 1));
int cur_tree_max_level_number = max_level_number;
int index = 0;
for (int level = 0; level < max_level; level++)
{
string line1 = string(max_level_number * 3 - 1, ' ');
int cur_level_number = min(count - int(pow(2, level)) + 1,
int(pow(2, level)));
bool isLeft = true;
for (int index_cur_level = 0; index_cur_level < cur_level_number;
index++, index_cur_level++)
{
putNumberInLine(indexes[index], line1, index_cur_level,
cur_tree_max_level_number * 3 - 1, isLeft);
isLeft = !isLeft;
}
cout << line1 << endl;
if (level == max_level - 1)
{
break;
}
string line2 = string(max_level_number * 3 - 1, ' ');
for (int index_cur_level = 0; index_cur_level < cur_level_number;
index_cur_level++)
{
putBranchInLine(line2, index_cur_level, cur_tree_max_level_number * 3 - 1);
}
cout << line2 << endl;
cur_tree_max_level_number /= 2;
}
}
private:
void putNumberInLine(int num, string &line, int index_cur_level,
int cur_tree_width, bool isLeft)
{
int sub_tree_width = (cur_tree_width - 1) / 2;
int offset = index_cur_level * (cur_tree_width + 1) + sub_tree_width;
assert(offset + 1 < line.size());
if (num >= 10)
{
line[offset + 0] = '0' + num / 10;
line[offset + 1] = '0' + num % 10;
}
else
{
if (isLeft)
line[offset + 0] = '0' + num;
else
line[offset + 1] = '0' + num;
}
}
void putBranchInLine(string &line, int index_cur_level, int cur_tree_width)
{
int sub_tree_width = (cur_tree_width - 1) / 2;
int sub_sub_tree_width = (sub_tree_width - 1) / 2;
int offset_left = index_cur_level * (cur_tree_width + 1) + sub_sub_tree_width;
assert(offset_left + 1 < line.size());
int offset_right = index_cur_level * (cur_tree_width + 1) + sub_tree_width
+ 1 + sub_sub_tree_width;
assert(offset_right < line.size());
line[offset_left + 1] = '/';
line[offset_right + 0] = '\\';
}
};
#endif
main.cpp：
#include"MinIndexHeap.h"
#include <ctime>
int main()
{
MinIndexHeap<int> minIndexHeap = MinIndexHeap<int>(100);
srand(time(NULL));
for (int i = 0; i < 15; i++)
{
minIndexHeap.insert(i, rand() % 100);
}
minIndexHeap.testPrint();
cout << endl;
while (!minIndexHeap.isEmpty())
{
cout << minIndexHeap.extractMin() << " ";
}
cout << endl;
system("pause");
return0;
}
运行一览：
程序 3：最小索引堆的再优化
MinIndexHeap.h：
#ifndef MININDEXHEAP_H
#define MININDEXHEAP_H
#include <iostream>
#include <string>
#include <cassert>
#include <algorithm>
using namespace std;
//最小索引堆：索引从0开始
template<typename Item>
class MinIndexHeap
{
private:
Item *data; //指向存储元素的数组
int *indexes; //指向存储索引的数组
int *reverse; //指向存储反向索引的数组
int count;
int capacity;
//私有函数，用户不能调用
//使用插入排序的优化方式进行优化
void shiftUp(int k)
{
Item e = data[indexes[k]];
int i = indexes[k];
//如果新添加的元素小于父节点的元素，则进行交换
while (k > 0 && data[indexes[(k - 1) / 2]] > e)
{
indexes[k] = indexes[(k - 1) / 2];
reverse[indexes[k]] = k;
k = (k - 1) / 2;
}
indexes[k] = i;
reverse[indexes[k]] = k;
}
//也是私有函数，用户不能调用
//使用插入排序的优化方式进行优化
void shiftDown(int k)
{
Item e = data[indexes[k]];
int i = indexes[k];
//只要当前节点有孩子就进行循环
while (2 * k + 1 < count)
{
// 在此轮循环中,data[indexes[k]]和data[indexes[j]]交换位置
int j = 2 * k + 1;
// data[indexes[j]]是data[indexes[j]]和data[indexes[j+1]]中的最小值
if (j + 1 < count && data[indexes[j + 1]] < data[indexes[j]])
{
j += 1;
}
if (e <= data[indexes[j]])
{
break;
}
indexes[k] = indexes[j];
reverse[indexes[k]] = k;
k = j;
}
indexes[k] = i;
reverse[indexes[k]] = k;
}
public:
MinIndexHeap(int capacity)
{
data = new Item[capacity];
indexes = newint[capacity];
reverse = newint[capacity];
//初始化reverse数组
for (int i = 0; i < capacity; i++)
{
reverse[i] = -1;
}
//计数器，这里索引等于计数器减一
count = 0;
this->capacity = capacity;
}
~MinIndexHeap()
{
delete []data;
delete []indexes;
delete []reverse;
}
int size()
{
return count;
}
bool isEmpty()
{
return count == 0;
}
void insert(int i, Item item)
{
//防止越界
assert(count <= capacity);
assert(i >= 0 && i <= capacity);
data[i] = item;
indexes[count] = i;
reverse[i] = count;
count++;
shiftUp(count - 1);
}
//取出最小的data
Item extractMin()
{
//首先要保证堆不为空
assert(count > 0);
Item ret = data[indexes[0]];
swap(indexes[0], indexes[count - 1]);
reverse[indexes[count - 1]] = -1;
reverse[indexes[0]] = 0;
count--;
shiftDown(0);
return ret;
}
//取出最小的data对应的index
int extractMinIndex()
{
assert(count > 0);
//对于外部来说，索引从0开始，所以要减一
int ret = indexes[0];
swap(indexes[0], indexes[count - 1]);
reverse[indexes[count - 1]] = -1;
reverse[indexes[0]] = 0;
count--;
shiftDown(0);
return ret;
}
Item getMin()
{
assert(count > 0);
return data[indexes[0]];
}
int getMinIndex()
{
assert(count > 0);
return indexes[0];
}
bool contain(int i){
assert(i >= 0 && i <= capacity);
//reverse数组在构造函数中都初始化为-1，
//所以拿-1做比较
return reverse[i] != -1;
}
Item getItem(int i)
{
assert(contain(i));
//对于外部来说，索引从0开始，
//对于内部来说，索引从1开始，
//所以要加一
return data[i];
}
//修改 index 对应的 data
void change(int i, Item newItem)
{
//防止越界和检查i是否在堆中，
//因为有可能已经取出去了
assert(contain(i));
data[i] = newItem;
// 找到indexes[j] = i, j表示data[i]在堆中的位置
// 之后尝试着shiftUp(j)一下, 再shiftDown(j)一下
//即看看能不能向上或向下移动以保持堆的性质
int j = reverse[i];
shiftUp(j);
shiftDown(j);
//先用O(1)的时间找到位置，再用O(lgn)的时间完成
//Shift Up和Shift Down，此时，该函数的时间复杂
//度就是O(lgn)级别的，如果有n个堆操作，总时间
//就是O(n*lgn)
//
//加入了反向查找后，性能得到了巨大的提升
}
public:
//在控制台打印测试用例
void testPrint()
{
//限制：只能打印100个元素以内的堆，因为控制台一行的字符数量有限
if (size() >= 100)
{
cout << "Fancy print can only work for less than 100 int";
return;
}
//限制：只能打印类型是int的堆
if (typeid(Item) != typeid(int))
{
cout << "Fancy print can only work for int item";
return;
}
cout << "The Heap size is: " << size() << endl;
cout << "data in heap: ";
for (int i = 0; i < size(); i++)
{
cout << data[i] << " ";
}
cout << endl;
cout << endl;
int n = size();
int max_level = 0;
int number_per_level = 1;
while (n > 0)
{
max_level += 1;
n -= number_per_level;
number_per_level *= 2;
}
int max_level_number = int(pow(2, max_level - 1));
int cur_tree_max_level_number = max_level_number;
int index = 0;
for (int level = 0; level < max_level; level++)
{
string line1 = string(max_level_number * 3 - 1, ' ');
int cur_level_number = min(count - int(pow(2, level)) + 1,
int(pow(2, level)));
bool isLeft = true;
for (int index_cur_level = 0; index_cur_level < cur_level_number;
index++, index_cur_level++)
{
putNumberInLine(indexes[index], line1, index_cur_level,
cur_tree_max_level_number * 3 - 1, isLeft);
isLeft = !isLeft;
}
cout << line1 << endl;
if (level == max_level - 1)
{
break;
}
string line2 = string(max_level_number * 3 - 1, ' ');
for (int index_cur_level = 0; index_cur_level < cur_level_number;
index_cur_level++)
{
putBranchInLine(line2, index_cur_level, cur_tree_max_level_number * 3 - 1);
}
cout << line2 << endl;
cur_tree_max_level_number /= 2;
}
}
private:
void putNumberInLine(int num, string &line, int index_cur_level,
int cur_tree_width, bool isLeft)
{
int sub_tree_width = (cur_tree_width - 1) / 2;
int offset = index_cur_level * (cur_tree_width + 1) + sub_tree_width;
assert(offset + 1 < line.size());
if (num >= 10)
{
line[offset + 0] = '0' + num / 10;
line[offset + 1] = '0' + num % 10;
}
else
{
if (isLeft)
line[offset + 0] = '0' + num;
else
line[offset + 1] = '0' + num;
}
}
void putBranchInLine(string &line, int index_cur_level, int cur_tree_width)
{
int sub_tree_width = (cur_tree_width - 1) / 2;
int sub_sub_tree_width = (sub_tree_width - 1) / 2;
int offset_left = index_cur_level * (cur_tree_width + 1) + sub_sub_tree_width;
assert(offset_left + 1 < line.size());
int offset_right = index_cur_level * (cur_tree_width + 1) + sub_tree_width
+ 1 + sub_sub_tree_width;
assert(offset_right < line.size());
line[offset_left + 1] = '/';
line[offset_right + 0] = '\\';
}
};
#endif
main.cpp：
#include"MinIndexHeap.h"
#include <ctime>
int main()
{
MinIndexHeap<int> minIndexHeap = MinIndexHeap<int>(100);
srand(time(NULL));
for (int i = 0; i < 15; i++)
{
minIndexHeap.insert(i, rand() % 100);
}
minIndexHeap.testPrint();
cout << endl;
while (!minIndexHeap.isEmpty())
{
cout << minIndexHeap.extractMin() << " ";
}
cout << endl;
system("pause");
return0;
}
运行一览：
【made by siwuxie095】
