实现堆。

2021 腾讯 wxg 后台开发面试题

堆的存储

堆的存储通过数组来实现, 由于其满足完全二叉树的性质.

则有**第i个节点(i从0开始算)**的

• 父节点: (i-1)/2 // 为负数时则说明父节点不存在
• 左右子节点: (i*2+1) 和 (i*2+2)

插入堆

给出一个数组存储的堆, 如果加入了新元素, 必须想办法保持堆的特性:
完全二叉 和 父节点小于等于其子节点

加入新元素后, 只需要不断与其父节点进行比较, 根据大小关系进行调整.
即分为两步:

1. 将新的数放入数组尾部.
2. 将最后一个数向上调整.

从堆中删除

堆结构仅支持从堆顶进行POP操作, 每次都能够POP出最小的元素.

POP以后堆结构即遭到破坏(缺失了首元素), 此时可以通过下列步骤恢复:

1. 将最后一个元素放到堆顶.
2. 将堆顶元素向下调整.

数组堆化

这一part要解决给出一个数组, 用这个数组构建堆的问题.

有以下两种思路:

1. 把数组里的数一个一个取出来, 插入堆中.
2. 对数组里的每一个非叶子节点的数进行向下调整的操作.

template <typename T>
class MaxHeap {
public:
    MaxHeap(int capacity = 10) {
        this->capacity = capacity;
        size = 0;
        heap = new T[capacity];
    }
    
    MaxHeap(T arr[], int n) {
        heap = new T[n];
        size = n;
        capacity = n;
        for (int i = 0; i < n; ++i) {
            heap[i] = arr[i];
        }
        
        for (int i = parent(n-1); i >= 0; --i) {
            siftDown(i);
        }
    }
    
    ~MaxHeap() {
        delete [] heap;
    }
    
    int getSize() {
        return size;
    }
    
    bool isEmpty() {
        return size == 0;
    }
    
    void add(T e) {
        heap[size] = e;
        ++size;
        siftUp(heap->getSize() - 1);
    }
    
    T findMax() {
        return heap[0];
    }
    
    T remove(int index) {
        T ret = heap[index];
        for (int)
    }
    
    T pop() {
        T ret = findMax();
        swap(heap[0], heap[heap->getSize() - 1]);
        --size;
        siftDown(0);
        return ret;
    }
    
private:   
    int parent(int index) {
        return (index - 1) / 2;
    }
    
    int leftChild(int index) {
        return index * 2 + 1;
    }
    
    int rightChild(int index) {
        return index * 2 + 2;
    }
    
    void siftUp(int k) {
        while (k > 0 && heap[parent(k)] < heap[k])) {
            swap(heap[parent(k)], heap[k]);
            k = parent(k);
        }
    }
    
    void siftDown(int k) {
        while (leftChild(k) < heap->getSize()) {
            int j = leftChild(k);
            if (j+1 < heap->getSize() && heap[j+1] > heap[j]) {
                // j = j + 1; 
                j = rightChild(k);
            }
            if (heap[k] >= heap[j]) break;
            
            swap(heap[k], heap[j]);
            k = j;
        }
    }
    
private:
    T *heap;
    int size;
    int capacity;
}