Talk:Heap (data structure)
From Wikipedia, the free encyclopedia
Contents |
[edit] 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? Jirka6 18:38, 25 February 2007 (UTC)
[edit] Definition
I was under the impression that heaps must also be complete trees...that is...the last level of the tree must be filled with a left to right ordering but maybe this is not true for all heaps...
- That only holds for binary heaps. --Mellum 09:59, 3 Dec 2004 (UTC)
- Imagine a scenario where the bottom level is completely full. If a new node were to be added to the heap, how could it maintain the property of being a complete binary tree, since the leftmost node would not be filled at the last level? Sheepdude 19:46, 20 April 2007 (UTC)
Let A and B be nodes of a heap, such that B is a child of A. The heap must then satisfy the following condition (heap property): key(A) ≥ key(B)
This is only for the special case of a max-heap, isn't it? --Abdull 17:38, 6 March 2006 (UTC)
[edit] complete table of run time complexity
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. Cyc 14:05, 2 May 2006 (UTC)
- That table is not correct. As the proof on the 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. Bender2k14 21:42, 12 October 2007 (UTC)
[edit] heapifying
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. Josh Froelich 16:43, 16 February 2007 (UTC)
[edit] 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.
