JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums Tutorial Discussions Data Structures Tutorial Priority Queues
 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.
 Forums Tutorial Discussions Data Structures Tutorial Priority Queues Previous Thread  |  Next Thread