堆 续8

xiaoxiao2021-02-27  137

----------------------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)级别的函数

//其中:遍历是nShift UpShift Downlgn

//

//之前的插入操作和删除操作,都能保证是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 UpShift 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 UpShift 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】

转载请注明原文地址: https://www.6miu.com/read-15032.html

最新回复(0)