概念

实现

概念

最大堆是二叉堆的两种形式之一。 根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者，称为大根堆,又称最大堆.

注意： ①堆中任一子树亦是堆。 ②以上讨论的堆实际上是二叉堆(Binary Heap)，类似地可定义k叉堆。

实现

view plaincopy to clipboardprint?

template<class T>

class MaxHeap {

public:

MaxHeap(int MaxHeapSize = 10);

~MaxHeap() {delete [] heap;}

int Size() const {return CurrentSize;}

T Max() {if (CurrentSize == 0)

throw OutOfBounds();

return heap[1];}

MaxHeap<T>& Insert(const T& x);

MaxHeap<T>& DeleteMax(T& x);

void Initialize(T a[], int size, int ArraySize);

void Deactivate() {heap = 0;}

void Output() const;

private:

int CurrentSize, MaxSize;

T *heap;

};

template<class T>

MaxHeap<T>::MaxHeap(int MaxHeapSize)

{

MaxSize = MaxHeapSize;

heap = new T[MaxSize+1];

CurrentSize = 0;

}

template<class T>

MaxHeap<T>& MaxHeap<T>::Insert(const T& x)

{

if (CurrentSize == MaxSize)

throw NoMem();

//为x寻找应插入的位置

//i从新的叶节点开始，并沿着树上升

int i = ++CurrentSize;

while (i != 1 && x > heap[i/2])

{

heap[i] = heap[i/2]; // 将元素下移

i /= 2; // 移向父节点

}

heap[i] = x;

return *this;

}

template<class T>

MaxHeap<T>& MaxHeap<T>::DeleteMax(T& x)

{

if (CurrentSize == 0)

throw OutOfBounds();

x = heap[1];

T y = heap[CurrentSize--]; //最后一个元素

// 从根开始, 为y寻找合适的位置

int i = 1, // 堆的当前节点

ci = 2; // i的子节点

while (ci <= CurrentSize)

{

// 使heap[ci] 是i较大的子节点

if (ci < CurrentSize

&& heap[ci] < heap[ci+1])

ci++;

// 能把y放入heap[i]吗?

if (y >= heap[ci])

break;//能

//不能

heap[i] = heap[ci]; // 子节点上移

i = ci; // 下移一层

ci *= 2;

}

heap[i] = y;

return *this;

}

template<class T>

void MaxHeap<T>::Initialize(T a[], int size, int ArraySize)

{

delete [] heap;

heap = a;

CurrentSize = size;

MaxSize = ArraySize;

// 产生一个最大堆

for (int i = CurrentSize/2; i >= 1; i--)

{

T y = heap[i]; // 子树的根

// 寻找放置y的位置

int c = 2*i; // c 的父节点是y的目标位置

while (c <= CurrentSize)

{

// 使heap[c]是较大的子节点

if (c < CurrentSize

&& heap[c] < heap[c+1])

c++;

// 能把y放入heap[c/2]吗?

if (y >= heap[c])

break; // 能

// 不能

heap[c/2] = heap[c]; // 子节点上移

c *= 2; // 下移一层

}

heap[c/2] = y;

}

}

template<class T>

void MaxHeap<T>::Output() const

{

cout << "The " << CurrentSize

<< " elements are"<< endl;

for (int i = 1; i <= CurrentSize; i++)

cout << heap[i] << ' ';

cout << endl;

}