堆heap

堆的存储

堆的结构：堆（二叉堆）实际上是完全二叉树，所以可以用数组来实现堆的结构。

便于检索
数组下标i从1开始，对于下标为i的节点，i/2为其父节点的下标，2i和2i+1为其左孩子，右孩子节点下标

堆的部分有序性：
MaxHeap任一节点的值大于或等于其子节点的值
MinHeap任一节点的值小于或者等于其子节点的值

---

堆（Binary Heap）的实现

实现最小堆代码(参考自geeksforgeeks:binary-heap)

/*用数组实现最小堆*/
#include<iostream>
using namespace std;

class MinHeap
{
private:
    int *heap;//实际上用vector更方便一点 
    int MaxLength;//数组大小
    int curlen;//数组当前长度
    void shiftUp(int index);//在尾部加入一个数，用递归和父亲节点比较
    void shiftDown(int index);//父节点和子节点比较，往下走（也是递归)
public:
    MinHeap(int *array,int length);//构造函数,调用了heaify()
    MinHeap();
    void heapify();//堆化
    void print();//打印数组
    void deleteMin();//用最后一个元素代替顶部元素，然后shiftDown(0)
    void insertElement(int element);//在尾部插入一个数，然后shiftUp(index)和父节点比较往上走

};
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) {//叶节点
        return;
    }
    int min = lchild;
    if (rchild<curlen && heap[min] > heap[rchild]) {//父节点和较小的子节点比较
        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]) {//父节点和较小的子节点比较
            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加了两个函数
    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();
        }
    }
};