Figure 2: The ExtractMin() consolidation process. (a) The heap after inserting values 0-12 and extracting 0. Now, start from 11 and consolidate the heap; (b) 10 and 11 both had degree zero, so were joined; (c) 8 and 9 were joined; (d) 8 and 10 both had degree one; (e) 7,6,5, and 4 were consolidated. (f) Eight and 4 both had degree two; (g) Finished. One has degree zero, 2 has degree one, 4 has degree three. Note that every element is smaller than all of its children.
BACK TO ARTICLE