接上篇

#include "../utils/common.hpp"
#include <iterator>
#include <utility>
#include <vector>

class MaxHeap {
private:
    vector<int> maxHeap;
    int left(int i) {
        return 2*i+1;
    }
    int right(int i) {
        return 2*i+2;
    }
    int parent(int i) {
        return (i-1)/2;
    }
    void siftUp(int i) {
        while (true) {
            int p = parent(i);
            if(p<0 || maxHeap[i] <=maxHeap[p]) {
                break;
            }
            swap(maxHeap[i],maxHeap[p]);
            i = p;
        }
    }
        void siftDown(int i) {

        while (true) {
            int l = left(i),r = right(i),ma = i;
            if(l < size() && maxHeap[l] > maxHeap[ma]) {
                ma = l;
            }
            if(r < size() && maxHeap[r] > maxHeap[ma]) {
                ma = r;
            }
            if(ma == i) {
                break;
            }
            swap(maxHeap[i],maxHeap[ma]);
            i = ma;
        }
    }
public:
    MaxHeap(vector<int> nums) {
        maxHeap = nums;
        for (int i = parent(size() -1); i >= 0; i --) {
            siftDown(i);
        }
    }
    int size() {
        return maxHeap.size();
    }
    bool isEmpty() {
        return size() == 0;
    }
    int peek() {
        return maxHeap[0];
    }
    void push(int val) {
        maxHeap.push_back(val);
        siftUp(size()-1);
    }
    void pop() {
        if(isEmpty()) {
            throw out_of_range("堆为空");
        }
        swap(maxHeap[0],maxHeap[size()-1]);
        maxHeap.pop_back();
        siftDown(0);
    }
    void printHeap() {
        cout << "堆的数组表示：";
        printVector(maxHeap);
        cout << "堆的树状表示：" << endl;
        TreeNode *root = vectorToTree(maxHeap);
        printTree(root);
        freeMemoryTree(root);
    }

    
};

int main() {
    vector<int> vec = {9,8,6,6,7,5,2,1,4,3,6,2};
    MaxHeap maxHeap(vec);
    cout << "\n输入列表并建堆后" << endl;
    maxHeap.printHeap();
    int peek = maxHeap.peek();
    cout << "\n堆顶元素为 " << peek << endl;

    /* 元素入堆 */
    int val = 7;
    maxHeap.push(val);
    cout << "\n元素 " << val << " 入堆后" << endl;
    maxHeap.printHeap();

    /* 堆顶元素出堆 */
    peek = maxHeap.peek();
    maxHeap.pop();
    cout << "\n堆顶元素 " << peek << " 出堆后" << endl;
    maxHeap.printHeap();

    /* 获取堆大小 */
    int size = maxHeap.size();
    cout << "\n堆元素数量为 " << size << endl;

    /* 判断堆是否为空 */
    bool isEmpty = maxHeap.isEmpty();
    cout << "\n堆是否为空 " << isEmpty << endl;
    return 0;
}

输出

输入列表并建堆后
堆的数组表示：[9, 8, 6, 6, 7, 5, 2, 1, 4, 3, 6, 2 ]堆的树状表示：
          /——— 2
     /——— 6
   |     \——— 5
   |          \——— 2
——— 9
   |          /——— 6
   |     /——— 7
   |   |     \——— 3
     \——— 8
        |     /——— 4
          \——— 6
               \——— 1

堆顶元素为 9

元素 7 入堆后
堆的数组表示：[9, 8, 7, 6, 7, 6, 2, 1, 4, 3, 6, 2, 5 ]堆的树状表示：
          /——— 2
     /——— 7
   |   |     /——— 5
   |     \——— 6
   |          \——— 2
——— 9
   |          /——— 6
   |     /——— 7
   |   |     \——— 3
     \——— 8
        |     /——— 4
          \——— 6
               \——— 1

堆顶元素 9 出堆后
堆的数组表示：[8, 7, 7, 6, 6, 6, 2, 1, 4, 3, 5, 2 ]堆的树状表示：
          /——— 2
     /——— 7
   |     \——— 6
   |          \——— 2
——— 8
   |          /——— 5
   |     /——— 6
   |   |     \——— 3
     \——— 7
        |     /——— 4
          \——— 6
               \——— 1

堆元素数量为 12

堆是否为空 0

提示：从右向左看输出，是想构建的结构化的树