堆的實作以及堆排序(最大堆，最小堆)

一.堆的概念

堆是一種特殊的資料結構，相當于數組實作的一顆二叉樹，但是和一般的二叉搜尋樹不同

1.堆分為最大堆（父結點的值必大于其孩子結點的值）和最小堆（父結點的值必小于其孩子結點的值）,

而二叉搜尋樹中左孩子結點的值小于父節點的值，右孩子結點的值大于父節點的值。

2.堆采用數組形式存儲，相較于二叉樹的連結清單結構減少記憶體消耗

3.堆排序的時間複雜度可以穩定在O(nlogn)，而當二叉樹為非平衡狀态時，相應操作的時間複雜度不能穩定

二.堆的應用

1.優先隊列

優先隊列的使用場景十分之廣，比如此時此刻你的計算機作業系統正在處理很多的程序，程序與程序之間存在着優先執行關系，對應的每個程序都有一個優先級。

舉個更簡單的例子：雲頂之弈中，很多英雄的技能會優先攻擊血量最少的敵方英雄。LoL中也存在着類似的技能機制。實質上就是一個動态的優先隊列。

2.索引堆

堆中的内容經過heapify後交換了位置，進而形成最大堆或者最小堆。對簡單的資料内容進行交換空間、時間消耗還不大，但是若對于上述提到的程序、英雄機關這些對象，操作起來則會比較麻煩并且很多情況下我們并不想改變元素的位置。

索引堆就是為了解決這個問題，對于原數組中的元素不進行交換，而是額外創造一個對應于原數組的索引數組（int[]），索引數組中每個元素記錄原數組中每個元素的索引，在索引數組中進行heapify交換索引位置，讓索引生成最大堆或者是最小堆，進而對于原數組沒有改變。

索引堆運用在優先隊列、圖的最小生成樹等算法當中。

3.堆排序

根據最大堆、最小堆堆頂元素的性質，進而可以實作堆排序，具體實作如下。

三.cpp實作

1.最大堆

根結點以1開始

template<typename T>
class MaxHeap{
private:
	T *arr;
	int count;
	int capacity;

	
	//核心代碼：shiftUp()、shiftDown()
	void shiftUp(int count){ //疊代條件：該節點的值大于父結點的值 且該節點不為根結點
		while(count>1 && arr[count/2]<arr[count]){
			swap(arr[count/2],arr[count]);
			count / =2;
		}
	}


	void shiftDown(int index){
		while(index*2<=count){ //疊代條件：某個結點存在左孩子結點
			int i = index*2;
			if(i+1<=count && arr[i]<arr[i+1])//如果右孩子存在  選擇左右孩子結點中值最大的結點
				i++;
			if(arr[index]>arr[i])
				break;
			swap(arr[i],arr[index]);
			index = i;
		}
	}
public:
	MaxHeap(int n){
		arr = new int[n+1];
		count = 0;
		capacity = n;
	}

	MaxHeap(int n,int *arr){  //param:  a Random Array(int)、array.length  
		arr = new int[n+1];
		for (int i = 0; i < n; ++i)
		{
			arr[i+1] = arr[i];
		}
		capacity=n;
		count = n;

		for (int i = n/2; i >0; --i) //n/2表示第一個非葉子結點的結點
		{							 //從n/2這個結點開始做shiftDown()操作 直至達到根結點
			shiftDown(i);
		}
	}

	void insert(T x){
		assert(count+1<capacity);
		arr[++count] = x;
		shiftUp(count);
	}

	T extractMax(){
		assert(count>=1);
		T max = arr[1];
		swap(arr[1],arr[count--])；
		shiftDown(1);
		return max;
	}
};
           

2.最小堆

根結點從0開始:

#include"iostream"
#include"assert.h"
using namespace std;


template<typename Item>
class MinHeap
{
private:
    /* data */
    int count;
    int capacity;
    Item *data;

    void shiftUp(int k){
        while(k-1>0 && data[(k-1-1)/2]>data[k-1] ){
            swap(data[k-1],data[(k-2)/2]);
            k = k/2;
        }
    }

    void shiftDown(int k){  //時間複雜度 logn
        while(2*k+1<count){
            int i = 2*k+1;
            if(2*k+2<count && data[i]>data[i+1])
                i++;
            if(data[i]>=data[k])
                break;
            swap(data[i],data[k]);
            k = i;
        }
    }
public:
    MinHeap(int n){
        data = new Item[n];
        count = 0;
        capacity = n;
    }

    void add(Item x){
        assert(count+1<=capacity);
        data[count++] = x;
        shiftUp(count); 
    }

    Item extractMin(){
        assert(count>0);
        Item k = data[0];
        swap(data[0],data[--count]);
        shiftDown(0);
        return k;
    }

    bool empty(){
        return count == 0;
    }
    
    ~MinHeap(){
        delete []data;
    }
};
           

四.堆排序及性能測試

1.最大堆排序

template<typename T>
void shiftDown(T arr[],int n,int index){
    //heapify條件  該節點至少存在左子樹
    while(2*index+1<n){
        int i=2*index+1;
        if(i+1<n && arr[i]<arr[i+1])
            i++;
        if(arr[index]>arr[i])
            break;
        swap(arr[index],arr[i]);
        index = i;
    }
}



template<typename T>
void heapSort(T arr[],int n){
    //heapify
    for(int i=(n-1-1)/2;i>=0;i--)
        shiftDown(arr,n,i);

    //将最大堆的堆頂交換至最後，再對剩餘元素進行heapify
    for(int i=n-1;i>0;i--){
        swap(arr[0],arr[i]);
        shiftDown(arr,i,0);
    }
}

           

2.性能測試

n=50000 測試範圍0~50000

測試随機生成以及完全有序兩種情況