1

I am confused as to the proper usage of the heapq._siftdown function. Can anybody explain what arguments I am supposed to pass it?

The python documentation states:

'heap' is a heap at all indices >= startpos, except possibly for pos.

pos is the index of a leaf with a possibly out-of-order value. Restore the heap invariant.

def _siftdown(heap, startpos, pos):

I tried this in the interpreter: 

>>> a = [1,2,9,4]
>>> heapq._siftdown(a,0,2)
>>> a
>>> [1, 2, 9, 4]

However, this does not work -- the list is not sorted, even though I have obeyed the input conditions.

xrisk
  • 3,790
  • 22
  • 45
  • 1
    [If you ask about the problem you need to solve, rather than the tool you're trying to use to solve it](http://meta.stackexchange.com/questions/66377/what-is-the-xy-problem), you'll get your problem solved much better and much faster. Why are you trying to use `heapq._siftdown`? – user2357112 May 22 '15 at 02:05
  • 1
    "the list is not sorted" - My psychic powers tell me OP is doing homework, specifically implementing [heapsort](http://en.wikipedia.org/wiki/Heapsort). OP: The heap invariant does not require the heap to be sorted. It just mandates that elements can be removed in sorted order using `heappop()`. – Kevin May 22 '15 at 02:37
  • 1
    @Kevin, if you must know - i need to implement a priority queue, for Dijkstra. But the keys of the priority queue change at runtime, so I need the decrease-key functionality, which is what _siftdown does as written in http://stackoverflow.com/questions/1465662/how-can-i-implement-decrease-key-functionality-in-pythons-heapq – xrisk May 22 '15 at 06:51
  • 1
    @xrisk: Then **ask** that question. Write something like "I have a heap created with `heapq` and I need to change the value of one of the elements. How do I do that?" Right now, you're running afoul of the [XY problem](http://meta.stackexchange.com/questions/66377/what-is-the-xy-problem). – Kevin May 22 '15 at 13:13

3 Answers3

1

It sifts down, unless you think it misbehaves. Heaps are not trivial. Search for sift down on the wikipedia page for heap. Or you may want to start at the top of the page and work your way there :).

Ariakenom
  • 204
  • 1
  • 5
  • By misbehaves, I mean it doesn't behave as according to this http://stackoverflow.com/questions/1465662/how-can-i-implement-decrease-key-functionality-in-pythons-heapq and https://hg.python.org/cpython/file/2.7/Lib/heapq.py#l242 – xrisk May 22 '15 at 06:55
  • 1
    @xrisk: It does exactly what the source code and Alex Martelli's answer state. The heap invariant is not "this list is sorted"; it would not be expected for a heap to be sorted after performing a sift-down. – user2357112 May 22 '15 at 07:50
  • 1
    @user2357112 aah, I just realized my mistake. Indeed the heap invariant is maintained. My bad. Should I delete the question? – xrisk May 22 '15 at 08:44
0

heapq.heapify() does not always guarantee to make an array sorted as we see it when it is printed. All it guarantees is that the first element that is the element at index 0 is the smallest of all. For some inputs, since things fall into place for example [3, 2] we see that after heapify the array to be sorted.

After heapify is called this explanation (from the source code) holds true:

Heaps are arrays for which a[k] <= a[2k+1] and a[k] <= a[2k+2] for all k, counting elements from 0. For the sake of comparison, non-existing elements are considered to be infinite. The interesting property of a heap is that a[0] is always its smallest element.

For the sift down, it just bubbles down a bigger value to its correct place, for example when you delete an element (pop) then the following steps happen:

  1. Index of the number you want to delete is looked up
  2. The Last element is put into that index, this might be bigger and can be breaking the binary tree rules.
  3. Then sift down is called to send this bigger value down to its correct place.

As such siftdown does not promise complete sorting of the array when we print it. For more implementation details you can lookup heapq.py file within python source.

To always get a sorted representation we can use something like this:

def heapify_demo(nums):
    
    heapq.heapify(nums)
    print(nums)
    print(heapq.nsmallest(len(nums), nums))


print(heapify_demo([1, 2, 9, 4]))
Sourabh Parime
  • 31
  • 3
-2

The proper usage is to not use it. It is an internal implementation detail; it may change behavior, change name, or be removed entirely in future versions. This is indicated by the _ on its name, and the fact that it isn't in the documentation.

user2357112
  • 260,549
  • 28
  • 431
  • 505
  • I know that -- but I do need to use it, and I'm not building something permanent. – xrisk May 22 '15 at 01:49
  • 4
    I'd appreciate it if you'd tell me how to make it work as intended, internal or not internal. – xrisk May 22 '15 at 01:50
  • @xrisk: You don't need to use it. It doesn't sound like you even know what it does. You have some task you need performed, and for some reason, you have decided that an internal implementation detail of `heapq` is the best way to perform the task. It isn't. – user2357112 May 22 '15 at 02:00
  • @xrisk: I don't understand what you want us to tell you. It is only intended to be called from within the heapq module itself. It has no notion of "work as intended." – Kevin May 22 '15 at 02:33
  • @user2357112 - Please see the comment that I added to the question just now. If you believe that the question need's rephrasing, I'll do it. – xrisk May 22 '15 at 06:56