用数组实现堆

这里实现一个最小堆

实现堆关键在于堆调整，堆有向上调整和向下调整，当pop堆顶元素的时候是弹出数组里面最小的元素，这个时候需要向下调整堆，把堆顶元素的值更新为数组末尾元素的值，然后从堆顶开始向下调整堆

代码语言：javascript复制

    int pop() {
        if(empty())
            return -1;
        int temp=data[0];
        std::swap(data[0],data[--heapSize]);
        adjustDown(0);
        return temp;
    }

从树根节点开始，找出左右子树中比自己更小的节点，交换值，然后从交换后的节点处继续往下寻找更小的节点，直到堆末尾或者没有更小的

代码语言：javascript复制

    void adjustDown(int root) {
        int left = 2 * root   1;
        int right = left   1;
        int next = root; // 找到比根节点小的
        if (left < heapSize && data[left] < data[next])
            next = left;
        if (right < heapSize && data[right] < data[next])
            next = right;
        if (next != root) {
            std::swap(data[next], data[root]);
            adjustDown(next);
        }
    }

push元素的时候先放到数组末尾，然后看看容量是不是满了，增长一下容量，开始从数组末尾向上调整堆 

代码语言：javascript复制

    void push(int value) {
        data[heapSize] = value;
          heapSize;
        if (heapSize == volume) {
            grow();
        }
        adjustUp();
    }

向上调整堆先找出当前节点的父节点，如果父节点是更大的节点，那么交换值后往上走，继续向上寻找更大的节点

代码语言：javascript复制

    void adjustUp() {
        int index=heapSize-1;
        int parent=(index-1)/2;
        while(index>0&&data[parent]>data[index]) {
            std::swap(data[index],data[parent]);
            index=parent;
            parent=(index-1)/2;
        }
    }

完整代码

代码语言：javascript复制

class Heap {
    int volume = 8;
    int heapSize = 0;
    int back = 0;
    int front = 0;
    int *data = nullptr;

    void grow() {
        int *temp = new int[2 * volume];
        for (int i = 0; i < volume;   i) {
            temp[i] = data[i];
        }
        delete[]data;
        data = temp;
        volume *= 2;
    }
    void adjustUp() {
        int index=heapSize-1;
        int parent=(index-1)/2;
        while(index>0&&data[parent]>data[index]) {
            std::swap(data[index],data[parent]);
            index=parent;
            parent=(index-1)/2;
        }
    }
    void adjustDown(int root) {
        int left = 2 * root   1;
        int right = left   1;
        int next = root; // 找到比根节点小的
        if (left < heapSize && data[left] < data[next])
            next = left;
        if (right < heapSize && data[right] < data[next])
            next = right;
        if (next != root) {
            std::swap(data[next], data[root]);
            adjustDown(next);
        }
    }

public:
    Heap() {
        data = new int[volume];
    }

    void push(int value) {
        data[heapSize] = value;
          heapSize;
        if (heapSize == volume) {
            grow();
        }
        adjustUp();
    }

    int pop() {
        if(empty())
            return -1;
        int temp=data[0];
        std::swap(data[0],data[--heapSize]);
        adjustDown(0);
        return temp;
    }
    int top() {
        if(empty())
            return -1;
        return data[0];
    }

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

    bool size() const {
        return heapSize;
    }
};

数组 data int parent root

0 人点赞