二叉堆的插入删除等操作C++实现

青旅半醒 2022-08-06 04:07 188阅读 0赞

有几种明显的方法实现优先队列：

1. 使用**简单链表**在表头以O(1)执行插入操作，遍历该链表需要O(N)。另一方法是始终保持表有序，插入操作代价为O(N)，deleteMin花费为O(1)。

2. 使用**二叉查找树**。插入、删除操作平均时间均为O(logN)。实现优先队列要删除最小元素，那么将会不断在左子树中删除，会损害树的平衡，会使右子树加重。这样，在最坏情况下，左子树为空，则树相当于链表，这样其操作的时间界限就会变为最坏情况。另外，查找树实现有些过分，因为它支持大量并不需要的操作。

**二叉堆是实现优先队列的常见方法**。它是完全二叉树，有规律可循，因此**可用数组实现而不使用链表**。如果从数组的下标为1的位置开始存元素（下标0处不存），那么数组中某位置i上的元素，其左孩子在位置2i，右孩子在2i+1位置上。

要快速找到最小值，则使用小根堆，根元素最小。

由于二叉堆是完全二叉树，因此其高度为不大于logN的最大整数。插入操作、删除操作的最坏时间为O(logN)，平均时间为O(logN)。

以下代码以vector容器为基本数组实现小根堆，使用泛型编程实现：

**这里用到了泛型编程，对于泛型编程有注意的地方，参考《[泛型编程注意不能将模板类的成员函数放在独立的实现文件中][Link 1]》。**

删除堆的过程就是要下滤的。  
而堆排序用到了删除堆的操作，因此，堆排序也是要下滤的。  
对任意输入序列建立堆也要下滤，因为该过程就是一系列元素排序的过程。

//6heap.h
    #ifndef TEST_HEAP_H
    #define TEST_HEAP_H
    
    #include "test.h"
    
    /*
    这里建立的是小根堆，元素存在vector容器中，根从下标为1的元素开始
    */
    template <typename T>
    class BinaryHeap {
    public:
        explicit BinaryHeap(int capacity = 100)
            :array(capacity + 1), current_size(0) {}
        explicit BinaryHeap(const vector<T>& items)
            :array(items.size() + 10), current_size(items.size()) {
            int i;
            for (i = 0; i < items.size(); i++)
                array[i + 1] = items[i];
            BuildHeap();
        }
    
        bool IsEmpty() const {
            return current_size == 0;
        }
    
        const T& FindMin() const {
            if (IsEmpty())
                cout << "No items in binary heap" << endl;
            return array[1];
        }
    
        /*
        堆的插入操作是“上滤”的过程。最坏时间为O(logN)，平均时间为O(logN)。
        先在堆的下一个空闲位置上建立一个空穴，如果这样不破坏堆的性质，那么插入完成。
        否则，将空穴父节点的元素移入空穴，这样空穴上升了一层，到达父节点的位置。
        继续该过程，直到插入值可以放入空穴为止。
        */
        void Insert(const T& value)    {
            if (current_size == array.size() - 1) //空间不够，重分配
                array.resize(array.size() * 2);
            int hole = ++current_size; //在堆的下一个空闲位置建立一个空穴
            /* 
            在空穴没上滤到根部并且插入值小于空穴父节点时，
            将父节点移入空穴，空穴位置上升一层 
            */
            for ( ; hole > 1 && value < array[hole / 2]; hole /= 2)
                array[hole] = array[hole / 2];
            array[hole] = value; //将值插入到合适位置
        }
    
        /*
        删除操作最坏时间为O(logN)，平均时间为O(logN)。
        删除最小值时，根成空穴，且堆要少一个元素，
        因此原堆的最后一个元素X将要放到堆的某个位置；
        如果X可以放到空穴中则完成；否则要将空穴的儿子中较小的元素放入空穴，空穴
        下移，重复该过程直到X可以放入空穴。
        */
        void DeleteMin() {
            if (IsEmpty())
                cout << "No items in binary heap" << endl;
            array[1] = array[current_size--];
            PercolateDown(1);
        }
    
        void DeleteMin(T& min_item) {
            if (IsEmpty())
                cout << "No items in binary heap" << endl;
            min_item = array[1];
            array[1] = array[current_size--];
            PercolateDown(1);
        }
    
        void MakeEmpty() {
            current_size = 0;
        }
    
        void PrintItems() {
            cout << "Items: ";
            int i = 1;
            while (i <= current_size) {
                cout << array[i++] << " ";
            }
            cout << endl;
        }
    
    private:
        int current_size;
        vector<T> array;
        /*
        建立堆的操作最坏时间为O(NlogN)，平均时间为O(N)
        建立堆的过程就是堆排序的过程
        */
        void BuildHeap() {
            int i;
            for (i = current_size / 2; i > 0; i--)
                PercolateDown(i);
        }
    
        /*
        该函数完成“下滤”过程。
        删除堆的过程就是要下滤的。
        而堆排序用到了删除堆的操作，因此，堆排序也是要下滤的。
        对任意输入序列建立堆也要下滤。
        该函数的做法是将插入值置入沿着从根开始
        包含最小儿子的一条路径上的正确位置
        */
        void PercolateDown(int hole) {
            int pos_child;
            T tmp = array[hole];
            //当空穴位置没有到达堆的尾部前，循环向下层找空穴位置
            for ( ; hole * 2 <= current_size; hole = pos_child) {
                pos_child = 2 * hole;
                /*
                下边语句是要将较小孩子的下标移入空穴，将空穴移入下一层。
                下边的pos_child != current_size条件是控制当堆的节点为偶数时情况，
                当堆节点为偶数时，最后一个非叶节点只有一个左孩子，则此时要找的
                较小孩子的下标就是左孩子的下标，即不用执行下边第一个if
                */
                if (pos_child != current_size && array[pos_child + 1] < array[pos_child])
                    pos_child++;
                if (array[pos_child] < tmp)  //如果较小孩子比父节点小，则空穴下移一层
                    array[hole] = array[pos_child];
                else
                    break;
            }
            array[hole] = tmp;
        }
    };
    #endif

//test.cpp
    #include "6heap.h"
    
    int main() {
        BinaryHeap<int> heap;
        heap.Insert(22);
        heap.Insert(12);
        heap.Insert(7);
        heap.Insert(1);
        heap.PrintItems();
    
        vector<double> dvec;
        int i;
        for (i = 10; i > 0; --i)
            dvec.push_back(i);
        BinaryHeap<double> dheap(dvec);
        dheap.PrintItems();
    
        heap.DeleteMin();
        heap.PrintItems();
    
        dheap.DeleteMin();
        dheap.DeleteMin();
        dheap.PrintItems();
        return 0;
    }

![Center][]

[Link 1]: http://blog.csdn.net/u013074465/article/details/42030093
[Center]: /images/20220806/d6d00bc7efd2448aa28b6bae25aff48b.png