Content deleted Content added
| (15 intermediate revisions by 13 users not shown) | |||
Line 1:
{{WikiProject
{{WikiProject Mathematics|priority=mid}}
{{WikiProject Computer science|importance=high}}
}}
== Unifying heaps ==
Line 180 ⟶ 183:
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''
# 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
# 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?
Line 193 ⟶ 196:
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)
| |||