Content deleted Content added
→min heap vs. max confusion: new section |
|||
| (37 intermediate revisions by 25 users not shown) | |||
Line 1:
{{WikiProject
{{WikiProject Mathematics|priority=mid}}
{{WikiProject Computer science|importance=high}}
}}
== Unifying heaps ==
The articles about heaps keep switching from min to max heaps and back (e.g. in this article the definition is for max heap while the complexity is for min heap.) I think we use consistently min-heap (or max-heap) and say in ONE place the other is just the opposite. What do you think? [[User:Jirka6|Jirka6]] 18:38, 25 February 2007 (UTC)
Line 21 ⟶ 25:
Anybody able to complete the table of the run time complexity?
It also would be nice to have more information than worst case or amortised cost.
[[User:Cyc|Cyc]] 14:05, 2 May 2006 (UTC)
:That table is not correct. As the proof on the [[Binary_heap#Building_a_heap|Binary Heap]] page shows, the running time for createHeap should be O(n). I will look into the createHeap times for the other heap implementations to see if they are wrong as well. [[User:Bender2k14|Bender2k14]] 21:42, 12 October 2007 (UTC)
Line 33 ⟶ 39:
You know you guys use the term heapifying in this topic? The topic is a mishmash of stuff in its current revision and I might clean it up like I did with [[tree (data structure)]]. Hope noone objects. [[User:Jfroelich|Josh Froelich]] 16:43, 16 February 2007 (UTC)
I
▲== == confusing ==
▲I''''m a graduate level EE who has been working for 20 years - and I don't understand. Perhaps the explanation could be less circular. Please keep in mind that this data is used by people who do not already know much about the subject.
:Agreed. This entry does not read well, and provides no explainations or definitions. <small>—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:Chieffancypants|Chieffancypants]] ([[User talk:Chieffancypants|talk]] • [[Special:Contributions/Chieffancypants|contribs]]) 03:47, 11 January 2008 (UTC)</small><!-- Template:Unsigned --> <!--Autosigned by SineBot-->
==Key needs to be explained in the definition==
It should be explained what a "key" is, becuase it is in the definition with no explanation, which makes the rest of the article usless to anyone who doesn't already know what a heap is, which in turn makes the article usless for %95 of people visiting the page because if you know what a key is there's only a small chance you don't know what a heap is. There isn't even a link (although, noe that a link to key wouldn't be adequeate in this case, because it is probably possible to give a short non-technical descriptioin of a "key"). [[Special:Contributions/76.175.72.51|76.175.72.51]] ([[User talk:76.175.72.51|talk]]) 17:19, 13 April 2009 (UTC)
: I agree. I don't know what kind of key this article is referring to, and so the introduction is meaningless to me. Could someone please explain what a heap key is? [[Special:Contributions/75.72.9.174|75.72.9.174]] ([[User talk:75.72.9.174|talk]]) 20:09, 21 December 2013 (UTC)
: Yes, "key" is one of several problems in the first paragraph [July2015 version]. A definition of "heap" should be given in the first paragraph. In my last LISP class this page developed into a source of jokes: "if you don't know what you are talking about, elevate the discussion to things that no one knows" and "now politicians will tell us about data structures", etc. [[User:Wrstark|wrstark]] ([[User talk:Wrstark|talk]]) 15:28, 22 July 2015 (UTC)wrstark
I know what is "key" is for sorting, but it's unclear to me what determines whether one item in the heap is the parent of another item. The article says that heaps can be used to implement stacks and queues, but the factor that determines parentage is needed to see the relationship. [[Special:Contributions/206.47.113.103|206.47.113.103]] ([[User talk:206.47.113.103|talk]]) 16:54, 10 January 2016 (UTC)
==Sublinear Claim==
Line 138 ⟶ 144:
Binomial heap should also have O(1) amortized insertion, as stated by its page. [[User:Gankro|Alexis Beingessner]] ([[User talk:Gankro|talk]]) 20:57, 24 February 2014 (UTC)
I have replaced the tables on each page with [[Template:Heap Running Times|a template]] with corrected data combined from both pages. I believe this fixes all the issues listed above. [[User:Wingedsubmariner|Wingedsubmariner]] ([[User talk:Wingedsubmariner|talk]]) 04:02, 1 September 2014 (UTC)
Binomial Heap should have O(1) find-min. It is trivial to keep track of the minimum element, just by using a constant amount of space to store it. <!-- Template:Unsigned --><small class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:Agnishom|Agnishom]] ([[User talk:Agnishom#top|talk]] • [[Special:Contributions/Agnishom|contribs]]) 05:41, 29 March 2017 (UTC)</small> <!--Autosigned by SineBot-->
== Link to "completeness" disambiguation page ==
Line 148 ⟶ 158:
There are two distinct articles, but in this one we see:
"... a heap is a complete binary tree ..." -- fixed with "If ..."
"... a heap is a complete binary tree ..." <span style="font-size: smaller;" class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/68.183.92.186|68.183.92.186]] ([[User talk:68.183.92.186|talk]]) 21:12, 13 May 2014 (UTC)</span><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->▼
== min heap vs. max confusion ==
Article states that " ...the word heap will always refer to a min-heap ..." and then refers to the diagram of a max-heap! -- fixed --- silly sentence removed
== Naming of operations ==
▲
== Incorrect short definition for heapify operation ==
To me, the short definition in the Operations section for heapify is not correct. It currently states: "heapify: create a heap out of given array of elements". However, to me this procedure is more for ensuring the heap contract. CLRS describes a MAX-HEAPIFY method in Section 6.2 ("Maintaining the heap property"). Skiena's Algorithm Design Manual, Section 4.3.3 ("Extracting the Minimum") explains "This percolate-down operation is also called heapify, because it merges two heaps (the subtrees below the original root) with a new key."
I personally find the "create-heap" operation definition ("create-heap: create an empty heap") a bit useless, adding to the confusion around "heapify" ("create a heap out of given array of elements"). To me, "create-heap" (what I would call "build-heap") should use the current definition of "heapify" and a new one presented based on CLRS, Skiena, et al.
[[User:Njuk-njuk|Njuk-njuk]] ([[User talk:Njuk-njuk|talk]]) 13:05, 21 August 2015 (UTC)
== Puzzling diagram ==
What is the sorting property for the heap in the diagram? It's a maxheap with all the perfect squares on the right main subtree and all the primes on the left, but I cannot come up with any rule for how the nodes were chosen beyond that.<!-- Template:Unsigned --><small class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:2601:19a:c102:74d5:7805:8d9:c4ee:94ab|2601:19a:c102:74d5:7805:8d9:c4ee:94ab]] ([[User talk:2601:19a:c102:74d5:7805:8d9:c4ee:94ab#top|talk]] • [[Special:Contributions/2601:19a:c102:74d5:7805:8d9:c4ee:94ab|contribs]]) </small>
== Clarifying min vs max, esp in the lead ==
I see several past comments about potential confusion surrounding min and max heaps but I think the problem is still there, specifically in the lead itself. There are three issues:
# The lead contradicts itself by defining ''heap property'' in terms of (first sentence) ''only'' "max heaps" but then goes on (fourth sentence) to include "min heaps".
# Even that restricted definition is further contradicted by the subsequent mentions of max and min heaps in terms of whether the correct relationships are (first sentence) "greater than" and "less than, or (third and fourth sentences) "greater than ''or equal to''" and "less than ''or equal to''" Searching around the web, "''the or equal to''" versions are by far the more common.
# HOWEVER, that then makes the references to "''root node''" confusing. Putting everything up to that point together it would appear that one could have a heap with multiple nodes, all with the same key (whatever that means). But in that case, what is meant by "highest" or "lowest" (in terms, respectively, of the roots of a ''max heap'' and ''min heap'')? Part of the problem here is, as someone earlier noted, it's not exactly clear what a key is. The addition of "''or value''" helps, but not enough. ''Is it really the case'' that one could have a parent and child with the same key (value)? If so, in what way are they: a. different nodes, and; b. parent and child? If not (esp. to a.), then why is the heap property defined in terms of "...or equal to" properties?
Until I hit the third of those points, I was just going to change the text from its current:
:In [[computer science]], a '''heap''' is a specialized [[Tree (data structure)|tree]]-based [[data structure]] that satisfies the ''heap property:'' if P is a parent [[Node (computer science)|node]] of C, then the ''key'' (the ''value'') of node P is greater than the key of node C. A heap can be classified further as either a "max heap" or a "'''min heap'''". In a max heap, the keys of parent nodes are always greater than or equal to those of the children and the highest key is in the root node. In a min heap, the keys of parent nodes are less than or equal to those of the children and the lowest key is in the root node.
to the following:
:In [[computer science]], a '''heap''' is a specialized [[Tree (data structure)|tree]]-based [[data structure]] that satisfies the following ''heap property:'' for all [[Node (computer science)|nodes]] C and P, if P is a parent of C, then the ''key'' (the ''value'') of P is either greater than or equal to (''max heap'') or less than or equal to (''mind heap'') the key of C. The node with the highest (''max heap'') or lowest (''min heap'') key is called the ''root'' node.
However, as I say that may still be an insufficient definition if you really can have a multiple-node heap but with all keys the same (i.e. as seems to be allowed by the "or equal to" component of the heap property. So I've left it unchanged for now. Maybe someone who knows this stuff better than I do could have a look? (And when you are, could you also check the grammar of my replacement definition. I'm trying to say that the relations are either ''all'' greater-than-or-equal to or ''all'' less-than-or-equal-to, and I could say it in formal logic, but in the plain English needed here I'm not completely sure I've captured the correct logical associations. Thx!) [[User:Sleety Dribble|Sleety Dribble]] ([[User talk:Sleety Dribble|talk]]) 20:08, 9 September 2017 (UTC)
:Totally agree about the internal contradiction, which was the most glaring issue. The "≥" versus ">" thing was an issue, and I addressed that too. Basically just used the text you proposed with a couple tweaks, closer to plain English than formal logic. Then I changed the definition of ''root node'' to dodge the case when all nodes have equal key.
:'''Details:''' Yes, I do think you can have a parent and child with the same key. NB I'm not a pro at this, though. They are different nodes in the sense that they are different "slots" in which things are stored. They're parent and child in that they satisfy the heap property. Kind of like how [1,2,3] and [1,2,2,3] and [7,7,7] all satisfy the "perfectly sorted list" property. If someone asks me to sort the list [7,7,7], maybe I'm temporarily bemused about why they're asking, or whether each 7 is "really" a different thing from its neighbors, but at the end of the day I just return a sorted list ;).
:Some things became clear to me when I read the NIST definition of ''key'' which is simply "The part of a group of data by which it is sorted [or] indexed...." It confused me initially too, because I'm used to think of ''key'' and ''value'' as different things. But I gather heaps are much more closely related to simple arrays than to key:value stores. The key ''is'' the value; there's no "separate" key by which to look up the value.
:Finally, I see what you mean about clarifying that "the relations are either ''all'' greater-than-or-equal to or ''all'' less-than-or-equal-to." I didn't yet address this, but I might. I like what NIST says about "more extreme than or equal to." Probably would require splitting 1st sentence into 2, which might be worth it.--[[User:Officiallyover|Officiallyover]] ([[User talk:Officiallyover|talk]]) 14:42, 8 October 2017 (UTC)
== New external links ==
I would like to offer my page of animated illustrations about the Heap (http://www.chrislaux.com/heap.html) for the external links section. I believe the animations explain the Heap nicely visually to go with the text-focussed explanations here.
[[User:Ctlaux|Ctlaux]] ([[User talk:Ctlaux|talk]]) 19:02, 3 September 2019 (UTC)
== Is first image ("Example of a binary max-heap...") correct? ==
I'm not a specialist, but is the first image (https://en.wikipedia.org/wiki/Heap_(data_structure)#/media/File:Max-Heap.svg) correct? In the "array representation" part (at image bottom) shouln't be slot with value "17" connecting with "2" and "7", instead of slot with value "3"?
[[User:Joint ventura|Joint ventura]] ([[User talk:Joint ventura|talk]]) 18:37, 11 February 2021 (UTC)
:(For the record), there was apparently a glitch, which [https://en.wikipedia.org/w/index.php?title=Heap_(data_structure)&diff=prev&oldid=1007288576 got fixed 6 days after you noticed it]. [[User:AHMartin|AHMartin]] ([[User talk:AHMartin|talk]]) 17:55, 15 January 2024 (UTC)
== Is "almost complete" correct? ==
As a beginner programmer, I was reading this article and was confused by the term "almost complete." There's no definition of the property on this page, and I can only find definitions of "almost complete" as it applies ''specifically'' to binary trees. However, it's clearly stated that a heap can be nonbinary. So does "almost complete" mean anything in this context? What exact property of heaps is it meant to describe?
(In addition, even for binary heaps, "almost complete" excludes the "perfect" case, which doesn't seem right at all.)
--[[Special:Contributions/66.189.60.1|66.189.60.1]] ([[User talk:66.189.60.1|talk]]) 01:09, 7 May 2021 (UTC)
:Given the existance of the (linked) article [[binary heap]], this Heap page has no business discussing the details of binary heap implementations. Also, the nomenclature variants for "complete", "perfect", "full", etc. binary trees are discussed in the (linked) article [[Binary tree#Types_of_binary_trees|Binary tree § Types_of_binary_trees]]. But since "almost complete" is a variant characterization of the tree underlying a binary heap's implementation, I changed it to "complete". Now this article uses the term consistently. [[User:AHMartin|AHMartin]] ([[User talk:AHMartin|talk]]) 18:36, 15 January 2024 (UTC)
| |||