完全二叉樹

?

首先讓我們回顧一下完全二叉樹的兩個性質:

? 性質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}：

(小頂堆)

(大頂堆)

?

大頂堆的設計

template <typename Type> class 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; };

大頂堆的實現

//構造 template <typename Type> MaxHeap<Type>::MaxHeap(int _maxSize): maxSize(_maxSize),currentSize(0) {if (maxSize < 1)throw std::length_error("heap size must >= 1");heapArray = new Type[maxSize]; } //析構 template <typename Type> MaxHeap<Type>::~MaxHeap() {delete []heapArray;heapArray = NULL;currentSize = 0; } //判空 template <typename Type> bool MaxHeap<Type>::isEmpty() const {return currentSize == 0; }

堆頂元素

//查看堆頂元素 template <typename Type> const Type &MaxHeap<Type>::top() const {if (isEmpty())throw std::underflow_error("heap is empty");return heapArray[0]; }

插入元素

//插入 template <typename Type> void MaxHeap<Type>::push(const Type &item) {//如果堆已滿, 則需要對堆進行擴充if (currentSize == maxSize){resize();}//將元素插入到堆的第一個空位置上heapArray[currentSize] = item;//維護堆的性質:向上滲透trickUp(currentSize);++ currentSize; } //向上滲透, 將剛剛插入的元素移動到合適的位置上 template <typename Type> void MaxHeap<Type>::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; } //將堆的大小加倍 template <typename Type> void MaxHeap<Type>::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; }

刪除堆頂元素

//刪除 template <typename Type> void MaxHeap<Type>::pop() {if (isEmpty())throw std::underflow_error("heap is empty");//只有一個元素if (currentSize == 1){heapArray[0].~Type();currentSize = 0;return ;}//顯示釋放堆頂元素heapArray[0].~Type();//直接將最有一個元素放到堆頂,//并且currentSize-1heapArray[0] = heapArray[-- currentSize];//此時如果破壞了堆的性質:向下滲透trickDown(0); } //向下滲透 template <typename Type> void MaxHeap<Type>::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;elselargeChild = leftChild;if (top >= heapArray[largeChild])break;//不然的話, 則需繼續向下滲透heapArray[index] = heapArray[largeChild];// index需要向下搜索index = largeChild;}//插入heapArray[index] = top; }

堆排序

? 堆排序就是將元素一個一個插入到堆中,?然后再一個一個的取出來;

//堆排序 template <typename Type> void heapSort(Type *begin, Type *end) {int size = end-begin;MaxHeap<Type> maxHeap(size);//存入堆中for (Type *current = begin; current < end; ++ current)maxHeap.push(*current);//從堆中取出while (begin != end){*begin = maxHeap.top();++ begin;maxHeap.pop();} }template <typename Type> 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; }

總結

以上是生活随笔為你收集整理的数据结构基础(19) --堆与堆排序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。