完全二叉树
首先让我们回顾一下完全二叉树的两个性质:
性质1:具有n个结点的完全二叉树的深度为[logn](向下取整)+1。
性质2:若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点：
(1) 若 i=1，则该结点是二叉树的根，无双亲，否则，编号为 [i/2](向下取整)的结点为其双亲结点； (2) 若 2i>n，则该结点无左孩子，否则，编号为 2i 的结点为其左孩子结点； (3) 若 2i+1>n，则该结点无右孩子结点，否则，编号为2i+1 的结点为其右孩子结点。
数组与完全二叉树
从上图可以看出, 如果完全二叉树从上到下且从左至右进行从0至n-1进行编号，则对完全二叉树的性质需要修改如下:
(1) 若 i=0，则该结点是二叉树的根，无双亲，否则，编号为 [(i-1)/2](向下取整)的结点为其双亲结点； (2) 若 2i+1>n，则该结点无左孩子，否则，编号为 2i+1 的结点为其左孩子结点； (3) 若 2i+2>n，则该结点无右孩子结点，否则，编号为2i+2 的结点为其右孩子结点。
大顶堆与小顶堆
堆是满足下列性质的数列{r1, r2, …，rn}：
(小顶堆)
(大顶堆)
大顶堆的设计
templateclass MaxHeap{public: MaxHeap(int _maxSize = 10); virtual ~MaxHeap(); bool isEmpty() const; void push(const Type &item); void pop(); const Type &top() const;private: //将堆的容量增大两倍 void resize(); //向上渗透 void trickUp(int index); //向下渗透 void trickDown(int index);private: Type *heapArray; int maxSize; //currentSize有两个含义: // 1.代表当前堆中已经存储的元素数 // 2.代表当前完全二叉树的第一个空位 int currentSize;};
大顶堆的实现
//构造templateMaxHeap ::MaxHeap(int _maxSize) : maxSize(_maxSize),currentSize(0){ if (maxSize < 1) throw std::length_error("heap size must >= 1"); heapArray = new Type[maxSize];}//析构template MaxHeap ::~MaxHeap(){ delete []heapArray; heapArray = NULL; currentSize = 0;}//判空template bool MaxHeap ::isEmpty() const{ return currentSize == 0;}
堆顶元素
//查看堆顶元素templateconst Type &MaxHeap ::top() const{ if (isEmpty()) throw std::underflow_error("heap is empty"); return heapArray[0];}
插入元素
//插入templatevoid MaxHeap ::push(const Type &item){ //如果堆已满, 则需要对堆进行扩充 if (currentSize == maxSize) { resize(); } //将元素插入到堆的第一个空位置上 heapArray[currentSize] = item; //维护堆的性质:向上渗透 trickUp(currentSize); ++ currentSize;}
//向上渗透, 将刚刚插入的元素移动到合适的位置上templatevoid MaxHeap ::trickUp(int index){ //根据完全二叉树的性质, 找到父节点 int parent = (index-1)/2; Type bottom = heapArray[index]; //循环终止条件 // 1. index = 0 //bottom元素插入到根节点 // 2. heapArray[parent] >= bottom //bottom插入到parent节点的一个子节点上 while ((index > 0) && (heapArray[parent] < bottom)) { //父节点下移 heapArray[index] = heapArray[parent]; index = parent; parent = (parent-1)/2; } //插入 heapArray[index] = bottom;}
//将堆的大小加倍templatevoid MaxHeap ::resize(){ int newSize = std::max(maxSize*2, 1); Type *newHeap = new Type[newSize]; for (int i = 0; i < currentSize; ++i) { newHeap[i] = heapArray[i]; } delete []heapArray; heapArray = newHeap; maxSize = newSize;}
删除堆顶元素
//删除templatevoid MaxHeap ::pop(){ if (isEmpty()) throw std::underflow_error("heap is empty"); //只有一个元素 if (currentSize == 1) { heapArray[0].~Type(); currentSize = 0; return ; } //显示释放堆顶元素 heapArray[0].~Type(); //直接将最有一个元素放到堆顶, //并且currentSize-1 heapArray[0] = heapArray[-- currentSize]; //此时如果破坏了堆的性质:向下渗透 trickDown(0);}
//向下渗透templatevoid MaxHeap ::trickDown(int index){ int largeChild; Type top = heapArray[index]; // 只需到达完全二叉树的最后一层 // 的上一层即可 // 循环的终止条件: // 1. index已经到达了最后一层(index >= currentSize/2 :找到了一个比较合适的位置) // 2. 在堆的中间找到了一个合适的位置(top >= heapArray[largeChild]) while (index < currentSize/2) { int leftChild = (index*2)+1; int rightChild = leftChild + 1; //如果有右儿子节点, 而且右儿子节点还大于左儿子节点 if (rightChild < currentSize && heapArray[rightChild] > heapArray[leftChild]) largeChild = rightChild; else largeChild = leftChild; if (top >= heapArray[largeChild]) break; //不然的话, 则需继续向下渗透 heapArray[index] = heapArray[largeChild]; // index需要向下搜索 index = largeChild; } //插入 heapArray[index] = top;}
堆排序
堆排序就是将元素一个一个插入到堆中, 然后再一个一个的取出来;
//堆排序templatevoid heapSort(Type *begin, Type *end){ int size = end-begin; MaxHeap maxHeap(size); //存入堆中 for (Type *current = begin; current < end; ++ current) maxHeap.push(*current); //从堆中取出 while (begin != end) { *begin = maxHeap.top(); ++ begin; maxHeap.pop(); }}template void heapSort(Type *array, int arraySize){ return heapSort(array, array+arraySize);}
附-测试代码:
int main(){ int array[20]; for (int i = 0; i < 20; ++i) { array[i] = rand()%100; cout << array[i] << ' '; } heapSort(array, 20); cout << endl; for (int i = 0; i < 20; ++i) { cout << array[i] << ' '; } cout << endl; return 0;}