Chapter 19: Binomial Heaps

Overview

This chapter and Chapter 20 present data structures known as mergeable heaps, which support the following five operations.

• 
  

  MAKE-HEAP() creates and returns a new heap containing no elements.



• 
  

  INSERT(H, x) inserts node x, whose key field has already been filled in, into heap H.



• 
  

  MINIMUM(H) returns a pointer to the node in heap H whose key is minimum.



• 
  

  EXTRACT-MIN(H) deletes the node from heap H whose key is minimum, returning a pointer to the node.



• 
  

  UNION(H₁, H₂) creates and returns a new heap that contains all the nodes of heaps H₁ and H₂. Heaps H₁ and H₂ are "destroyed" by this operation.

In addition, the data structures in these chapters also support the following two operations.

• 
  

  DECREASE-KEY(H, x, k) assigns to node x within heap H the new key value k, which is assumed to be no greater than its current key value.^[1]
  



• 
  

  DELETE(H, x) deletes node x from heap H.

As the table in Chapter 6), work well. Operations other than UNION run in worst-case time O(lg n) (or better) on a binary heap. If the UNION operation must be supported, however, binary heaps perform poorly. By concatenating the two arrays that hold the binary heaps to be merged and then running MIN-HEAPIFY (see Exercise 6.2-2), the UNION operation takes Θ(n) time in the worst case.

Figure 19.1: Running times for operations on three implementations of mergeable heaps. The number of items in the heap(s) at the time of an operation is denoted by n.

Chapter 20, we shall explore Fibonacci heaps, which have even better time bounds for some operations. Note, however, that the running times for Fibonacci heaps in Section 6.5, when we use a mergeable heap in an application, we often store a handle to the corresponding application object in each mergeable-heap element, as well as a handle to corresponding mergeable-heap element in each application object. The exact nature of these handles depends on the application and its implementation.

Section 19.1 defines binomial heaps after first defining their constituent binomial trees. It also introduces a particular representation of binomial heaps. Section 19.2 shows how we can implement operations on binomial heaps in the time bounds given in Part V, our default mergeable heaps are mergeable min-heaps, and so the operations MINIMUM, EXTRACT-MIN, and DECREASE-KEY apply. Alternatively, we could define a mergeable max-heap with the operations MAXIMUM, EXTRACT-MAX, and INCREASE-KEY.