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
AutoC 0 Junior Poster in Training
ArkM 1,090 Postaholic
What is it: a linked binary min heap? Why linked? Why binary? Why min?..
AutoC 0 Junior Poster in Training
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...
ArkM 1,090 Postaholic
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
http://compsci.learnhub.com/lesson/page/864-building-blocks-for-data-structures
There is max heap in your terms here...
Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.