I need to code a linked binary min heap.Everywhere I go its an array based min heap..can someone direct me to some pseudocode for a linked min heap?

Thanks for any help

8 Years
Discussion Span
Last Post by ArkM

instead of using an array for the heap I'm using a linked list type of heap because my elements in the heap are constantly changing..its like a tree with lptr and rptr...


From http://www.cs.brown.edu/courses/cs157/lectureNotes/huffman.pdf :

What are heaps? Viewed abstractly, heaps are nearly complete binary trees (every level is filled completely except possible for the bottom level which is filled from the left up to a point) which satisfy the heap property: every node has a key which is greater than or equal to the key of its parent.
- To find the minimum, just look at the root.
- To remove the minimum, replace it with the last key x (the one in the rightmost node of the bottom level; that node is removed), and once x is at the root, repeatedly swap x with the smaller of its two children until the heap property is satisfied.
- To insert a new value y, just add a node to the tree, at the first available spot (the leftmost non-existent node at the bottom level), put y in it, and repeatedly swap y with its parent until the heap property is satisfied.

See also nice pictures in
There is max heap in your terms here...

This question has already been answered. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.