JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
Priority Queues | Reply
Very good article.

Comment for the Priority Queue section: I think the following sentence "In general, element 0 of the array is the root, and elements k + 1 and k + 2 are the children of element k" should say "and elements 2k + 1 and 2k + 2 are the children of element k".
Re: Priority Queues (response to post by christoph.albre) | Reply
I agree completely I was actually coming here to make the same comment. That error needs to be corrected to prevent mis-leading people who may be learning these concepts for the first time.
Re: Priority Queues (response to post by edcoyne) | Reply
Is it a coincidence that you made this post exactly one year after the thread has been started?
Re: Priority Queues (response to post by christoph.albre) | Reply
Another more subtle issue in this section is this sentence in the second last paragraph: "If the new root node is larger than its left child, then the root is swapped with its left child, in order to maintain the property that the root is always less than its children."

Actually, the new root node should be swapped with either its left child or its right child, whichever has a higher priority. It is misleading as the author originally writes.
Re: Priority Queues (response to post by lcfr) | Reply
I was coming here to make the same point. Consider the following heap:


10
/ \
8 4


If this is a min-heap, this violates the conditions as the root should always be less than its children. If we then swap the left child, we get


8
/ \
10 4


which still violates the property (root is still greater than its right child). If, however, we swap with the smallest child, we get


4
/ \
8 10


and the property holds. So in a min-heap, we should swap with the smallest child, and in a max-heap we should swap with the largest child.
Re: Priority Queues (response to post by christoph.albre) | Reply
Both errors reported in this thread are corrected.
RSS