堆（Heap）¶

优先队列(Priority Queue)¶

特殊的队列，元素按照一定的优先级顺序（如key值大小）排列，每次出队的是优先级最高的元素，而不是最先进入队列的元素。
实现：数组和链表都可实现，但是插入、删除操作总有一个时间复杂度较高。
考虑用二叉树实现

定义¶

堆也称为优先队列，是一种特殊的树形数据结构，满足如下性质：

堆是用数组表示的完全二叉树，除了底层从右到左填充可能有空缺外，其余层都是满的。
任一节点的关键字是其子树所有节点的最大值或最小值：
- 最大堆/大顶堆：任一节点的关键字是其子树所有节点的最大值
- 最小堆/小顶堆：任一节点的关键字是其子树所有节点的最小值

数组索引

堆的根节点是数组的第一个元素，即A[1]
若节点a[i]的父节点存在，则其父节点为a[(i-1)/2]
若节点a[i]的左孩子存在，则其左孩子为a[2i]
若节点a[i]的右孩子存在，则其右孩子为a[2i+1]

操作¶

定义结构体：

    typedef struct HeapStruct *MaxHeap;
    struct HeapStruct {
        ElementType *Elements;// the array storing elements in heap
        int Size;// current number of elements in heap
        int Capacity;// maximum number of elements in heap
    }

创建堆

    MaxHeap CreateHeap( int MaxSize ) {
        MaxHeap H = (MaxHeap)malloc(sizeof(struct HeapStruct));
        H -> Elements = malloc((MaxSize + 1) * sizeof (ElementType)); 
        // index starts from 1,so the size is MaxSize + 1
        H -> Size = 0;
        H -> Capacity = MaxSize;
        H -> Elements[0] = MaxData;
        // set the 0th element as the maximum value, 
        return H;
    }

插入元素:

为满足完全二叉树这一性质，插入的初始位置只能是当前数组的下一个空位

为保证堆的有序性，这里采取上浮，即将新插入的元素与其父节点比较，若大于父节点，则将父节点下移，直到找到合适的位置插入新元素

    void Insert( MaxHeap H, ElementType item ) {
        // insert item into the heap H, H -> Elements[0] is the maximum value
        int i;
        if( IsFull(H) ) {
            printf("The heap is full\n");
            return;
        }

        for( i = ++H -> Size; H -> Elements[i/2] < item; i /= 2 ) {
            H -> Elements[i] = H -> Elements[i/2];
        }// Compare and move the parent node down
        H -> Elements[i] = item;
    }

哨兵(index = 0)的作用是在比较时，避免在数组的边界处进行额外的判断，提高效率。

删除最大元素:

删除最大元素后，为保证堆的有序性，这里采取下沉，即将最后一个元素放到根节点，然后将根节点与其左右孩子中较大的一个比较，若小于孩子节点，则将孩子节点上移，直到找到合适的位置

    ElementType DeleteMax( MaxHeap H ) {
        // delete the maximum element from the heap
        int Parent, Child;
        ElementType MaxItem, temp;
        if( IsEmpty(H) ) {
            printf("The heap is empty\n");
            return;
        }// if the heap is empty
        MaxItem = H -> Elements[1];
        // take the maximum element of root
        temp = H -> Elements[H -> Size--];
        //  take the last element of the heap and reset the size at the same time
        for( Parent = 1; Parent * 2 <= H -> Size;/*判别是否有儿子*/ Parent = Child ) {//for loop is to find the right position for temp(the position is denoted by Parent)
            Child = Parent * 2;//point to the left child
            if( (Child != H -> Size)/* 若等则无右儿子 */ && (H -> Elements[Child] < H -> Elements[Child + 1]) ) {
                // if the right child is larger than the left child
                Child++;// find the larger child
            }
            if( temp >= H -> Elements[Child] ) { //比左右儿子都大，无需调整
                break;
            } else {
                H -> Elements[Parent] = H -> Elements[Child];//左右儿子中的较大者上移，赋值给parent
            }
        }
        H -> Elements[Parent] = temp;
        return MaxItem;
    }

建立（最大）堆：

挨个插入：时间复杂度为\(O(N \logN)\)

将N个元素按输入顺序存入，先满足完全二叉树的结构特性再从最后一个非叶节点开始调整节点位置使之满足最大堆的有序性：时间复杂度为\(O(N)\)

    void PercDown( MaxHeap H, int p ) {
        // adjust the position of the element at index p
        int Parent, Child;
        ElementType X;
        X = H -> Elements[p];
        for( Parent = p; Parent * 2 <= H -> Size; Parent = Child ) {
            Child = Parent * 2;
            if( (Child != H -> Size) && (H -> Elements[Child] < H -> Elements[Child + 1]) ) {
                Child++;
            }
            if( X >= H -> Elements[Child] ) {
                break;
            } else {
                H -> Elements[Parent] = H -> Elements[Child];
            }
        }
        H -> Elements[Parent] = X;
    }
    void BuildHeap( MaxHeap H ) {
        // build a max heap
        int i;
        for( i = H -> Size / 2; i > 0; i-- ) {
            PercDown( H, i );
        }
    }

这是一个可视化网站

这是另一个可视化网站

d-Heaps¶

d-Heap是一种多叉堆，即每个节点有d个孩子
d-Heap比二叉堆低，因此插入操作时间复杂度为\(O(\log_d N)\)

最后更新: 2024年10月2日 14:45:20
创建日期: 2024年4月8日 14:02:06

堆 （Heap）¶

优先队列(Priority Queue)¶

定义¶

操作¶

d-Heaps¶

堆（Heap）¶