关于堆的描述可以参考:
http://www.cs.auckland.ac.nz/~jmor159/PLDS210/heaps.html
我的实现没有用二叉树,而是用数组。上文提到,由于堆是一种complete树(complete,和完全树略有区别),即子节点的上层是完全树,而子节点从左向右严格排列,这种数据结构可以用数组很好模拟。从第一层第一个节点为1开始,从左到右从上到下依次存储。则,对于某个索引为i的节点,其左子节点和右子节点的索引分别为:
i * 2, i * 2 + 1
C++代码:
#include <iostream>
using namespace std;
template<class T>
class doubleHeap
{
public:
doubleHeap(
int _size,
int _type // 1 : max heap 2 : min heap
);
void extractTop(T &top);
void deleteTop();
bool addElement(T _new_element);
bool empty();
bool full();
void printHeap(int root, int level); // for debug
private:
void swap(int i, int j);
int leftChild(int i);
int rightChild(int i);
int parent(int i);
bool comp(int i, int j); // if the nodes should exchange
private:
T *data;
int max_size;
int size;
int type;
};
template<class T>
doubleHeap<T>::doubleHeap(int _size, int _type)
{
max_size = 10;
if(_size >= 10)
max_size = _size;
data = new T[max_size];
size = 0;
type = 1; // default max heap
if(_type == 1 || type == 2)
type = _type;
}
template<class T>
void doubleHeap<T>::extractTop(T &top)
{
if(size == 0)
return;
top = data[0];
}
template<class T>
void doubleHeap<T>::deleteTop()
{
if(size == 0)
return;
data[0] = data[size - 1];
size --;
int cur = 0; // start from the root
int lChildIndex;
int rChildIndex;
// begin exchanging the node and check if it's been a heap
while(true)
{
if(cur >= size) // the heap is null
break;
rChildIndex = rightChild(cur);
lChildIndex = leftChild(cur);
if(lChildIndex >= size) // right child and left child has been a null
break;
else if(rChildIndex >= size) // rightChild null, left not
{
if(comp(cur, lChildIndex))
{
swap(cur, lChildIndex);
cur = lChildIndex;
}
else
break; // has been a heap
}
else // left and right are not null
{
if(comp(cur, rChildIndex) || comp(cur, lChildIndex))
{
if(comp(lChildIndex, rChildIndex))
{
swap(cur, rChildIndex);
cur = rChildIndex;
}
else
{
swap(cur, lChildIndex);
cur = lChildIndex;
}
}
else
break;
}
}
}
template<class T>
bool doubleHeap<T>::addElement(T _new_element)
{
data[size] = _new_element;
size ++;
int cur = size - 1;
int parentIndex;
while(true)
{
if(cur == 0)
break;
parentIndex = parent(cur);
if(comp(parentIndex, cur))
{
swap(cur, parentIndex);
cur = parentIndex;
}
else
break;
}
}
template<class T>
bool doubleHeap<T>::empty()
{
return size == 0;
}
template<class T>
bool doubleHeap<T>::full()
{
return max_size == size;
}
template<class T>
void doubleHeap<T>::swap(int i, int j)
{
T ex;
ex = data[i];
data[i] = data[j];
data[j] = ex;
}
template<class T>
int doubleHeap<T>::leftChild(int i)
{
return 2 * (i + 1) - 1;
}
template<class T>
int doubleHeap<T>::rightChild(int i)
{
return 2 * (i + 1);
}
template<class T>
int doubleHeap<T>::parent(int i)
{
return (i + i) / 2 - 1;
}
template<class T>
bool doubleHeap<T>::comp(int i, int j)
{
if(type == 1) // max heap
{
return data[i] < data[j];
}
else // min heap
{
return data[i] > data[j];
}
}
template<class T>
void doubleHeap<T>::printHeap(int root, int level)
{
int i;
if(root >= size)
return;
printHeap(leftChild(root), level + 1);
for(i = 0; i < level; i ++)
cout << "\t";
cout << data[root] << endl;
printHeap(rightChild(root), level + 1);
}
int main()
{
int a[] = {1, 10, 6, 23, 7, 8, 90, 12, 45, 76, 33, 25, 3, 17, 70, 10};
int i, aLen = 16, e;
doubleHeap<int> maxHeap(100, 1);
for(i = 0; i < aLen; i ++)
{
maxHeap.addElement(a[i]);
}
maxHeap.printHeap(0, 0);
// heap sort
while(!maxHeap.empty())
{
maxHeap.extractTop(e);
cout << e << " ";
maxHeap.deleteTop();
}
return 0;
}
输出:
1
17
45
12
76
10
33
10
90
8
25
7
70
6
23
3
90 76 70 45 33 25 23 17 12 10 10 8 7 6 3 1
原文链接: https://www.cnblogs.com/waytofall/archive/2012/04/10/2440722.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/46719
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!