用数组实现堆

叶茂林

发布于 2024-07-07 08:51:39

530

发布于 2024-07-07 08:51:39

这里实现一个最小堆

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

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

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

    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元素的时候先放到数组末尾，然后看看容量是不是满了，增长一下容量，开始从数组末尾向上调整堆

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

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

    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;
        }
    }

完整代码

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;
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-07-06，如有侵权请联系 cloudcommunity@tencent.com 删除

数组