4 Priority Queues(Heaps)

ADT

Objects: A finite ordered list with zero or more elements.

Operations:

• PriorityQueue Initialize(int MaxElements);
• void Insert(ElementType X, PriorityQueue H);
• ElementType DeleteMin(PriorityQueue H);
• ElementType FindMin(PriorityQueue H);

4.1 Simple Implementations

Linked list is better since there is never more deletions than insertion.

• Array:
  • Insertion -- add one item at the end ~ $\mathrm{\Theta }(1)$
  • Deletion
    • find the largest/smallest key ~ $\mathrm{\Theta }(n)$
    • remove the item and shift array ~ $O(n)$
• Linked List:
  • Insertion -- add to the front of the chain ~ $\mathrm{\Theta }(1)$
  • Deletion
    • find the largest/smallest key ~ $\mathrm{\Theta }(n)$
    • remove the item ~ $\mathrm{\Theta }(1)$
• Ordered Array:
  • Insertion
    • find the proper position ~ $O(n)$
    • shift array and add the item ~ $O(n)$
  • Deletion -- remove the item ~ $\mathrm{\Theta }(1)$
• Ordered Linked List:
  • Insertion
    • find the proper position ~ $O(n)$
    • add the item ~ $\mathrm{\Theta }(1)$
  • Deletion -- remove the first/last item ~ $\mathrm{\Theta }(1)$

4.2 Binary Heap

4.2.1 Structure Property:

A binary tree with $n$ nodes and height $h$ is complete if its nodes correspond(相对应) to the nodes numbered from 1 to $n$ in the perfect binary tree of height $h$.

A complete binary tree of height $h$ has between $2^h$ and $2^{h+1}-1$ nodes.

$h=[logN]$ if logN is not an integer, then h++.

We can use an array BT[n+1] to represent it.(BT[0] is not used)

If a complete binary tree with $n$ nodes is represented sequentially, then for any node with index $i$, $0<i<n$, we have:

index of $parent(i)=\{\begin{array}{c}[\frac{i}{2}]ifi\ne 1\\ Noneifi=1\end{array}$

index of $left\mathrm{\_}child(i)=\{\begin{array}{c}2iif2i\le n\\ Noneif2i\ge n\end{array}$

index of $right\mathrm{\_}child(i)=\{\begin{array}{c}2i+1if2i+1\le n\\ Noneif2i+1\ge n\end{array}$

4.2.2 Heap Order Property

A min tree is a tree in which the key value in each node is no larger than the key values in its children (if any). A min heap is a complete binary min tree.

4.2.3 Basic Heap Operations

4.2.3.1 Insertion

The possible position for a new node is only since a heap must be a complete binary tree.

/*H->Elements[0] is a sentinel*/
void Insert(ElementType X, PriorityQueue H)
{
    int i;
    if(IsFull(H))
    {
        Error("Priority queue is full");
        return;
    }
    for( i=++H->Size; H->Elements[i/2]; i/=2)
        H->Elements[i] = H->Elements[i/2];
    H->Elements[i]=X;
}

T(N)=O(log N)

4.2.3.2 DeleteMin

ElementType DeleteMin(PriorityQueue H)
{
    /*Percolate Down*/
    int i, Child;

    ElementType MinElement, LastElement;
    if(IsEmpty(H))
    {
        Error("Priority queue is empty");
        return H->Elements[0];
    }
    MinElement=H->Elements[1];
    LastElement=H->Elements[H->Size--];
    for(i=1;i*2<=H->Size;i=Child)
    {
        Child=i*2;
        if(Child!=H->Size && H->Elements[Child+1]<H->Elements[Child])
            Child++;
        if(LastElement>H->Elements[Child])
            H->Elements[i]=H->Elements[Child];
        else
            break;
    }
    H->Elements[i]=LastElement;
    return MinElement;
}

T(N)=O(log N)

4.2.3.3 Other Heap Operations

Finding any key except the minimum one will have to take a linear scan through the entire heap.

4.2.3.3.1 DecreaseKey(P,$\mathrm{\Delta }$,H)

Percolate up

4.2.3.3.2 IncreaseKey(P,$\mathrm{\Delta }$,H)

Percolate down

4.2.3.3.3 Delete(P,H)

DecreaseKey(P,$\mathrm{\infty }$,H);DeleteMin(H)

4.2.3.3.4 BuildHeap(H)

N successive Insertions

Time complexity is too low.

First, use the keys build a complete binary tree. Then, percolate down from the last parent node in $h-1$ height. Considering the worst case, the times of percolating down is the sum of height of each node. $sum={\displaystyle \sum _{i=0}^h(h-i)\times 2^i}$

Note

[Theorem] For the prefect binary tree of height $h$ containing $2^{h+1}-1$ nodes, the sum of heights of the nodes is $2^{h+1}-1-(h+1)$

T(N) = O(N)

4.3 d-Heaps

All nodes have $d$ children.

• Shall we make $d$ as large as possible?
• DeleteMin will take $d-1$ comparsions to find the smallest child. Hence the total time complexity would be $O(dlo{g}_{d}N)$
• $\ast 2$ or $/2$ is merely a bit shift, but $\ast d$ or $/d$ is not.
• When the prtority queue is too large to fit entirely in main memory, a d-heap will become interesting.

---

最后更新: 2023年11月20日 20:54:37
创建日期: 2023年11月15日 17:30:52