----------------------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 = new int[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"); return 0; } |
运行一览：
程序 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 = new int[capacity]; reverse = new int[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"); return 0; } |
运行一览：
程序 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 = new int[capacity]; reverse = new int[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"); return 0; } |
运行一览：
【made by siwuxie095】