----------------------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】