堆结构的实现

1. 堆结构就是用数组实现的完全二叉树结构
2. 完全二叉树中如果每棵子树的最大值都在顶部就是大根堆
3. 完全二叉树中如果每棵子树的最小值都在顶部就是小根堆
4. 堆结构的 heapInsert （上移） 与 heapify （下沉）操作
5. 堆结构的增大和减少
6. 优先级队列结构，就是堆结构

完全二叉树：对于 i i i 节点，左孩子为 2 i + 1 2i + 1 2i+1， 右孩子为 2 i + 2 2i + 2 2i+2，父节点为 ( i − 1 ) / 2 (i - 1) / 2 (i−1)/2

#include 
using namespace std;


//大根堆
class MyMaxHeap {
private :
    int *heap;
    int limit;
    int heapSize;
public:
    MyMaxHeap(int limit) {
        heap = new int[limit];
        this->limit = limit;
        heapSize = 0;
    }

    bool empty() {
        return heapSize == 0;
    }

    bool isFull() {
        return heapSize == limit;
    }
    
    //新加入的数，停在了index位置，依次往上移动
    //移动到0位置或者比父节点值小，停止
    void heapInsert(int *arr, int index) {
        //包含了两个终止条件：
        //index == 0 或 干不掉父节点
        while (arr[index] > arr[(index - 1) / 2]) {
            swap(arr, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    //从index位置往下看，不断下沉
    //当较大的孩子不必index位置的数大 或者 已经没有孩子了，停止
    void heapify(int *arr, int index, int heapSize) {
        int left = index * 2 + 1;
        while (left < heapSize) { //如果存在左孩子
            //先考虑是否存在右孩子，若存在，把较大孩子的下标给largest
            int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
            //孩子节点和index这个父节点比较值的大小
            largest = arr[largest] > arr[index] ? largest : index;
            //父节点胜出，下沉停止
            if (largest == index) break;

            //index和较大的孩子互换
            swap(arr, largest, index);
            index = largest;
            left = index * 2 + 1;
        }
    }

    void push(int value) {
        if (heapSize == limit) {
            cout << "The heap is full!" << endl;
            return ;
        }

        heap[heapSize] = value;
        heapInsert(heap, heapSize++);
    }

    //返回最大值,并且在大根堆中把最大值删掉
    //剩下的数，依然保持大根堆性质
    int pop() {
        int ans = heap[0];
        swap(heap, 0, --heapSize);
        heapify(heap, 0, heapSize);
        return ans;
    }

    void swap(int *arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    void print() {
        for (int i = 0; i < heapSize; i++) {
            cout << heap[i] << " ";
        }
        cout << endl;
    }
};

//for test
class RightMaxHeap {
private:
    int *arr;
    int limit;
    int size;
public:
    RightMaxHeap(int limit) {
        arr = new int[limit];
        this->limit = limit;
        size = 0;
    }

    bool empty() {
        return size == 0;
    }

    bool isFull() {
        return size == limit;
    }

    void push(int value) {
        if (size == limit) {
            cout << "The heap is full" << endl;
            return ;
        }

        arr[size++] = value;
    }

    int pop() {
        int maxValInd = 0;
        for (int i = 0; i < size; i++) {
            if (arr[i] > arr[maxValInd]) {
                maxValInd = i;
            }
        }
        int ans = arr[maxValInd];
        arr[maxValInd] = arr[--size];
        return ans;
    }

    void print() {
        for (int i = 0; i < size; i++) {
            cout << arr[i] << " ";
        }
        cout << endl;
    }
};

int main() {
    srand(time(0));
    int value = 1000;
    int limit = 100;
    int testTime = 1000000;

    bool success = true;
    for (int i = 0; i < testTime + 1; i++) {
        int curLimit = rand() % limit + 1;
        MyMaxHeap myHeap(curLimit);
        RightMaxHeap test(curLimit);

        int curOpTimes = rand() % limit;

        for (int j = 0; j < curOpTimes; j++) {
            if (myHeap.empty() != test.empty()) {
                cout << "Oops! empty() function occurs error!" << endl;
                success = false;
                break;
            }

            if (myHeap.isFull() != test.isFull()) {
                cout << "Oops! isFull() function occurs error!" << endl;
                success = false;
                break;
            }

            if (myHeap.empty()) {
                int curValue = rand() % value;
                myHeap.push(curValue);
                test.push(curValue);
            } else if (myHeap.isFull()) {
                if (myHeap.pop() != test.pop()) {
                    cout << "Oops! pop() function occurs error!" << endl;
                    success = false;
                    break;
                }
            } else {
                if (((rand() % 101)/ (double)101) < 0.5) {
                    int curValue = rand() % value;
                    myHeap.push(curValue);
                    test.push(curValue);
                } else {
                    int ans1 = myHeap.pop();
                    int ans2 = test.pop();
                    if (ans1 != ans2) {
                        myHeap.print();
                        test.print();
                        cout << "ans1 = " << ans1 << ", ans2 = " << ans2 << endl;
                        cout << "Oops! pop() function occurs error again!" << endl;
                        success = false;
                        break;
                    }
                }
            }
        }
        if (!success) break;
        if (i && i % 10000 == 0) { cout << i << " cases passed!" << endl; }
    }

    cout << "finish!" << endl;

    return 0;
}

其中 heapInsert 和 heapify 操作的时间复杂度都是 O ( l o g n ) O(logn) O(logn)。

问：如果数组的 0 ~ i 范围上本来已经是满足大根堆结构了，但是如果其中的某个位置 x 处的值发生了变化，如何将 0 ~ i 范围上调整为大根堆呢？

答：很简单，依次执行 heapInsert(arr, x) 和 heapify(arr, x, i + 1)，这两个操作中只有一个会执行。