10-2 Mergeable heaps using linked lists

A mergeable heap supports the following operations: $\text{MAKE-HEAP}$ (which creates an empty mergeable heap), $\text{INSERT}$, $\text{MINIMUM}$, $\text{EXTRACT-MIN}$, and $\text{UNION}$. Show how to implement mergeable heaps using linked lists in each of the following cases. Try to make each operation as efficient as possible. Analyze the running time of each operation in terms of the size of the dynamic set(s) being operated on.

a. Lists are sorted.

b. Lists are unsorted.

c. Lists are unsorted, and dynamic sets to be merged are disjoint.

In all three cases, $\text{MAKE-HEAP}$ simply creates a new list $L$, sets $L.head = \text{NIL}$, and returns $L$ in constant time. Assume lists are doubly linked. To realize a linked list as a heap, we imagine the usual array implementation of a binary heap, where the children of the $i$th element are $2i$ and $2i + 1$.

a. To insert, we perform a linear scan to see where to insert an element such that the list remains sorted. This takes linear time. The first element in the list is the minimum element, and we can find it in constant time. $\text{EXTRACT-MIN}$ returns the first element of the list, then deletes it. Union performs a merge operation between the two sorted lists, interleaving their entries such that the resulting list is sorted. This takes time linear in the sum of the lengths of the two lists.

b. To insert an element $x$ into the heap, begin linearly scanning the list until the first instance of an element $y$ which is strictly larger than $x$. If no such larger element exists, simply insert $x$ at the end of the list. If $y$ does exist, replace $y \text t$ by $x$.

This maintains the min-heap property because $x \le y$ and $y$ was smaller than each of its children, so $x$ must be as well.

Moreover, $x$ is larger than its parent because $y$ was the first element in the list to exceed $x$. Now insert $y$, starting the scan at the node following $x$. Since we check each node at most once, the time is linear in the size of the list.

To get the minimum element, return the key of the head of the list in constant time.

To extract the minimum element, we first call $\text{MINIMUM}$. Next, we'll replace the key of the head of the list by the key of the second smallest element $y$ in the list. We'll take the key stored at the end of the list and use it to replace the key of $y$. Finally, we'll delete the last element of the list, and call $\text{MIN-HEAPIFY}$ on the list.

To implement this with linked lists, we need to step through the list to get from element $i$ to element $2i$. We omit this detail from the code, but we'll consider it for runtime analysis. Since the value of $i$ on which $\text{MIN-HEAPIFY}$ is called is always increasing and we never need to step through elements multiple times, the runtime is linear in the length of the list.

EXTRACT-MIN(L)
    min = MINIMIM(L)
    linearly scan for the second smallest element, located in position i
    L.head.key = L[i]
    L[i].key = L[L.length].key
    DELETE(L, L[L.length])
    MIN-HEAPIFY(L[i], i)
    return min

MIN-HEAPIFY(L[i], i)
    l = L[2i].key
    r = L[2i + 1].key
    p = L[i].key
    smallest = i
    if L[2i] != NIL and l < p
        smallest = 2i
    if L[2i + 1] != NIL and r < L[smallest]
        smallest = 2i + 1
    if smallest != i
        exchange L[i] with L[smallest]
        MIN-HEAPIFY(L[smallest], smallest])

Union is implemented below, where we assume $A$ and $B$ are the two list representations of heaps to be merged. The runtime is again linear in the lengths of the lists to be merged.

UNION(A, B)
    if A.head == NIL
        return B
    x = A.head
    while B.head != NIL
        if B.head.key ≤ x.key
            INSERT(B, x.key)
            x.key = B.head.key
            DELETE(B, B.head)
        x = x.next
    return A

c. Since the algorithms in part (b) didn't depend on the elements being distinct, we can use the same ones.