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
What is it: a linked binary min heap? Why linked? Why binary? Why min?..
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...
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...