//
// Created by 罗炳国 on 2023/9/20.
//

#ifndef PFJ_CODE20_PRIORYQUEUE_H
#define PFJ_CODE20_PRIORYQUEUE_H
#include "commonHeader.h"

// 大根堆
class myHeap {
public:
    myHeap(int size) : heapSize_(0) {
        for (int i = 0; i < size; i++) {
            data.push_back(0);
        }
    }
    void push(int val) {
        if (heapSize_ > data.capacity())
            return;
        data[heapSize_] = val;
        heapInsert(data, heapSize_);
        heapSize_++;
    }

    void pop() {
        if (heapSize_ <= 0)
            return;
        vecSwap(data, 0, --heapSize_);
        heapify(data, 0);
    }

    int top() {
        return data[0];
    }

    int heapSize() {
        return heapSize_;
    }

    bool isEmpty() {
        return heapSize_ == 0;
    }

private:
    void heapInsert(vector<int> &arr, int index) {

        int pindex = index / 2;
        while (arr[index] > arr[pindex]) {
            vecSwap(arr, index, pindex);
            index = pindex;
            pindex = index / 2;
        }

    }

    void heapify(vector<int> &arr, int index) {
        int left = index * 2 + 1;
        while (left < heapSize_) { // 如果有左孩子
            int largest = left + 1 < heapSize_ && arr[left + 1] > arr[left] ? left + 1 : left;
            largest = arr[largest] > arr[index] ? largest : index;
            if (largest == index)
                break;
            vecSwap(arr, largest, index);
            index = largest;
            left = index * 2 + 1;
        }
    }
private:
    int heapSize_;
    vector<int> data;
};

void heapTest() {
    vector<int> arr {1, 4, 89, 23, 13, 8, 6, 7, 86, 65, 43};
    class myHeap heap(20);
    int len =  arr.size();
    for (int i = 0; i < len; i++) {
        heap.push(arr[i]);
    }
    while (!heap.isEmpty()) {
        int val = heap.top();
        std::cout << val << " ";
        heap.pop();
    }
}


#endif//PFJ_CODE20_PRIORYQUEUE_H