堆heap

堆的存儲

堆的結(jié)構(gòu)：堆（二叉堆）實際上是完全二叉樹，所以可以用數(shù)組來實現(xiàn)堆的結(jié)構(gòu)推溃。

便于檢索
數(shù)組下標(biāo)i從1開始冲粤，對于下標(biāo)為i的節(jié)點，i/2為其父節(jié)點的下標(biāo)梯捕，2i和2i+1為其左孩子，右孩子節(jié)點下標(biāo)

堆的部分有序性：
MaxHeap任一節(jié)點的值大于或等于其子節(jié)點的值
MinHeap任一節(jié)點的值小于或者等于其子節(jié)點的值

堆（Binary Heap）的實現(xiàn)

實現(xiàn)最小堆代碼(參考自geeksforgeeks:binary-heap)

/*用數(shù)組實現(xiàn)最小堆*/
#include<iostream>
using namespace std;

class MinHeap
{
private:
    int *heap;//實際上用vector更方便一點 
    int MaxLength;//數(shù)組大小
    int curlen;//數(shù)組當(dāng)前長度
    void shiftUp(int index);//在尾部加入一個數(shù)襟铭，用遞歸和父親節(jié)點比較
    void shiftDown(int index);//父節(jié)點和子節(jié)點比較寒砖，往下走（也是遞歸)
public:
    MinHeap(int *array,int length);//構(gòu)造函數(shù),調(diào)用了heaify()
    MinHeap();
    void heapify();//堆化
    void print();//打印數(shù)組
    void deleteMin();//用最后一個元素代替頂部元素，然后shiftDown(0)
    void insertElement(int element);//在尾部插入一個數(shù)哩都，然后shiftUp(index)和父節(jié)點比較往上走

};
MinHeap::MinHeap(int *array, int length) {
    MaxLength = length;
    curlen = length;
    heap = new int(length);
    for (int i = 0; i < length; i++) {
        heap[i] = array[i];
    }
    heapify();//建立最小堆
}
MinHeap::MinHeap(){}
void MinHeap::print() {
    for (int i= 0; i < curlen; i++) {
        cout << heap[i]<<" ";
    }
    cout << endl;
}
void MinHeap::heapify() {
    for (int i = (curlen - 1) / 2; i >= 0; i--) {
        shiftDown(i);
    }
}
void MinHeap::shiftUp(int index) {
    int child = index;
    int parent = (index - 1) / 2;
    if (child == 0)return;
    if (heap[child] < heap[parent]) {
        swap(heap[child], heap[parent]);
        shiftUp(parent);
    }
}
void MinHeap::shiftDown(int index) {
    int parent = index;
    int lchild = parent * 2 + 1;
    int rchild = lchild + 1;
    if (lchild >= curlen) {//葉節(jié)點
        return;
    }
    int min = lchild;
    if (rchild<curlen && heap[min] > heap[rchild]) {//父節(jié)點和較小的子節(jié)點比較
        min = rchild;
    }
    if (heap[parent] > heap[min]) {
        swap(heap[parent], heap[min]);
        shiftDown(min);
    }

    /*for (int i = parent; parent*2 < MaxLength; parent = child) {
        child = 2 * parent + 1;
        if (heap[child] < heap[child + 1]) {//父節(jié)點和較小的子節(jié)點比較
            child++;
        }
        if (heap[parent] > heap[child]) {
            swap(heap[parent], heap[child]);
        }
        else {
            break;
        }
    }*/
}
void MinHeap::deleteMin() {
    //即刪掉最頂上的
    if (curlen > 0) {
        heap[0] = heap[curlen - 1];//用最后一個替代
        curlen--;
        shiftDown(0);
    }
    else {
        cout << "the heap is empty!" << endl;
        return;
    }
    
}
void MinHeap::insertElement(int element) {
    if (curlen == MaxLength) {
        cout << "the heap is full!" << endl;
    }
    else {
        heap[curlen] = element;
        curlen++;
        shiftUp(curlen-1);
    }
}

Heap Sort堆排序

比如就用上面的最小堆咐汞，每次都輸出最頂上的值（一定是最小值）,直到刪完堆

//給MinHeap加了兩個函數(shù)
    int getCurLen() { return curlen; }
    int topMin() { if (curlen > 0)return heap[0]; else return -1; }

class HeapSort
{
public:
    HeapSort(MinHeap heap) {
        while (heap.getCurLen() >0) {
            cout << heap.topMin() << " ";
            heap.deleteMin();
        }
    }
};