Binomial, Fibonacci, and Pairing Heaps:Pseudocode Summaries of the Algorithms.

Pseudocode Summaries of the Algorithms

This section provides pseudocode reflecting the above algorithm descriptions. The procedures, link and insert, are sufficiently common with respect to all three data structures, that we present them first, and then turn to those procedures having implementations specific to a particular data structure.

Link and Insertion Algorithms

Function link(x,y){

// x and y are tree roots. The operation makes the root with the

// larger key the leftmost child of the other root. For binomial and

// Fibonacci heaps, the rank field of the prevailing root is

// incremented. Also, for Fibonacci heaps, the node becoming the child

// gets unmarked if it happens to be originally marked. The function

// returns a pointer to the node x or y that becomes the root.

Binomial Heap-Specific Algorithms

Function Meld(H,I){

// The forest lists of H and I are combined and consolidated -- trees

// having common rank are linked together until only trees of distinct

// ranks remain. (As described above, the process resembles binary

// addition.) A pointer to the resulting list is returned. The

// original lists are no longer available.

Pairing Heap-Specific Algorithms