堆數據結構的實現以及堆排序

1、堆的數據結構使用數組進行存儲的

2、堆的數據結構按照完全二叉樹的結構進行描述，所以這裡關於堆的孩子節點和父節點的關系，構成了堆數據中數據獲取的一個入口，下標為i的父節點的兩個孩子節點的下標分別是2*i ,2*i+1 不同的起始下標，表示可能有所不同。

3、最大堆可以用於排序，復雜度在O(Nlog(N)),對還是實現優先權隊列的數據結構基礎

4、下面的代碼詳細描述了最大堆的一些關鍵操作

#ifndef MAXHEAP_H
#define MAXHEAP_H
#include <memory.h>
#include <iostream>
using namespace std;

/**
    最大堆
*/

class MaxHeap
{
    public:
        int heapSize;
        int * heap;
    public:
        MaxHeap();
        MaxHeap(int heapSize);
        virtual ~MaxHeap();

        void output_heap();
        void init_heap(int a[],int n);

        int left(int i);
        int right(int i);

        void max_heapify(int i);
        void max_heapify2(int i);

        void build_max_heap();
        void heap_sort();

};

#endif // MAXHEAP_H

#include "MaxHeap.h"

MaxHeap::MaxHeap(){
}

MaxHeap::~MaxHeap(){
    delete []heap;
}

MaxHeap::MaxHeap(int heapSize):heapSize(heapSize){
    heap = new int [heapSize] ;
    memset(heap,0,sizeof(int)*heapSize);
}

//左孩子的index
int MaxHeap::left(int i){//下標從0開始的原因
    return 2*i+1;
}

//右孩子的index
int MaxHeap::right(int i){
    return 2*i +2;
}

/**
    輸出堆的內容
**/
void MaxHeap::output_heap(){
    for(int i=0;i<heapSize;++i){
        cout<<heap[i]<<" ";
    }
    cout<<endl;
}

/**
    利用數組初始化堆內容
**/
void MaxHeap::init_heap(int a[], int n){
    if(n>heapSize)return ;
    else{
        heapSize=n;
        //memcpy(heap,a,heapSize);
        for(int i=0;i<heapSize;++i){
            heap[i]=a[i];
        }
    }

}

/**
    調整堆內數組使得其滿足堆的性質
    調整從i節點開始，這個操作可以保證i節點及其子孫節點都滿足
    最大堆的特點
*/

void MaxHeap::max_heapify(int i){

    int l= left(i);
    int r= right(i);
    int max_index=0;
    //最大孩子的下標
    if(l<heapSize&&heap[l]>heap[i]){
        max_index=l;
    }else {
        max_index=i;
    }
    if(r<heapSize&&heap[r]>heap[max_index]){
        max_index=r;
    }

    if(max_index!=i){
        swap(heap[i],heap[max_index]);
        max_heapify(max_index);//防止造成子孫節點中出現不滿足堆的性質的情況發生
    }
}

//堆調整的非遞歸代碼實現

void MaxHeap::max_heapify2(int i){
    while(i<heapSize/2){
        int l = left (i);
        int r = right (i);
        int max_index=0;
        if(r<heapSize){
            max_index = heap[l] > heap[r] ? l : r;
            max_index = heap[max_index] > heap[i] ? max_index : i;
        }else{
            max_index = heap[l] > heap[i] ? l:i;
        }
        if(max_index!=i){
            swap(heap[i],heap[max_index]);
            i = max_index;
        }
    }
}

/**
    堆的建立操作
*/

void MaxHeap::build_max_heap(){
    for(int i= heapSize/2 +1;i>=0;--i){//從第一個非葉子節點開始調整為最大堆特征
        max_heapify(i);
    }
}

/**
    堆排序，將最後一個元素同堆頂元素交換
    每次都能保證取得的是當前最大的元素
    max_heapfy(0),調整第一個元素
**/

void MaxHeap::heap_sort(){
    build_max_heap();
    int t = heapSize;
    for(int i=heapSize-1;i>0;--i){
        swap(heap[i],heap[0]);
        heapSize--;
        max_heapify(0);//取出之後對造成的不滿足最大堆進行調整
    }
    heapSize=t;
}