Talk:Heap (data structure)

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)

I agree. Bender2k14 (talk) 00:06, 15 October 2009 (UTC)

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)

You are talking about a perfect tree, not a complete tree. See Types of binary trees. Bender2k14 (talk) 00:16, 15 October 2009 (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)

Yes, special in the sense that a heap is either a minheap or a maxheap. Bender2k14 (talk) 00:11, 15 October 2009 (UTC)

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)

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)

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"). 76.175.72.51 (talk) 17:19, 13 April 2009 (UTC)

Sublinear Claim

I just removed the claim that heaps can be used to find the max, min, both the max and min, median, or k-th largest element in sublinear time because that is not true. You have to look at each element at least once, so the running time is at least linear. Bender2k14 (talk) 00:20, 15 October 2009 (UTC)

I'm pretty sure that the sublinear claim refers to finding these elements after the heap has been constructed. Otherwise that claim would be pointless, and should be removed altogether. Paradoctor (talk) 06:45, 10 November 2009 (UTC)

The current statement "Finding the min, max, both the min and max, median, or even the k-th largest element can be done in linear time using heaps" also seems spurious. Firstly, you can easily find min, max and both min and max in linear time without using any kind of special data structure. And … can you really find the median in linear time in any way in which a heap is instrumental? (The standard linear median-finding algorithm doesn't use a heap.) You can find the k-th largest element in linear time with a heap 'if' you assume that k is a constant. Otherwise, if you don't want k popping up in the running time, using the same linear selection algorithm as for the median would be the solution. No heap involved, though. The most natural claims to have in this bullet point (related to selection) would be that it can find the k-th largest or smallest item in (for example) O(n lg k) or O(n + k lg k) time. Mlhetland (talk) 19:58, 12 July 2010 (UTC)

I removed the corresponding section according to the above discussion. --mellum (talk) 13:05, 2 August 2010 (UTC)

It's easy to find min/max in O(1) using heaps, and update them in O(ln(n)). You can't do that with the linear algorithm, it takes O(n) each and every time. After thinking about it for a while, I came up with O(1) for finding the median also using min/max heaps that update in O(ln n). But I added a ref tag.- Wolfkeeper 13:53, 2 August 2010 (UTC)

Brodal queue

Fibonacci queue cites this paper. From the abstract:

“ An implementation of priority queues is presented that supports the operations MakeQueue, FindMin, Insert, Meld and DecreaseKey in worst case time O(1) and DeleteMin and Delete in worst case time O(log n). The space requirement is linear. The data structure presented is the first achieving this worst case performance. ”

I think this should be mentioned here. Paradoctor (talk) 12:01, 7 November 2009 (UTC)

Weak heaps?

Is there any particular reason why weak heaps are not mentioned? Maybe this variant is not so well known? --188.126.207.212 (talk) 17:46, 23 August 2010 (UTC)

If you can write up something about weak heaps with proper sources, be bold. Qwertyus (talk) 15:04, 19 January 2011 (UTC)

Rm pseudo queues

I've removed all reference to "Pseudo Queues". I've never heard of them, and the reference given seems to have nothing to do whatsoever with heaps/priority queues. Qwertyus (talk) 15:09, 19 January 2011 (UTC)

Paring Heap Amortized Linear Time Insert Operation

Hi folks,

why is in the pairing heap implementation the insert operation denoted as amortized linear? Shouldn't it be linear without amortized analysis?

Grettings!