2

My code looks like this, where heap is a list:

 heap[0] = heap.pop()

The problem is it does not work when popping the only item. According to python wiki, popping last element is O(1). (I also want to remove the last element)

So far what I've come up with:

last_element = heap.pop()  # I don't want to catch potential IndexError here
try:
    heap[0] = last_element
except IndexError:
    heap.append(last_element)

which is a lot longer

or this

if len(heap) != 1:
    heap[0] = heap.pop()

which should be slower.

Is there a more pythonic way to do this? Internally python maybe does not even resize the array.

UPDATE: I need O(1) access to elements at given indeces (so it cannot be a linked list).

ShadowRanger
  • 143,180
  • 12
  • 188
  • 271
Adam
  • 1,724
  • 4
  • 21
  • 31
  • Does `heap[0] = heap.pop(-1)` even work for larger lists, though? For example, if `heap` is `[1,2,3]`, then you want it to become `[3,1,2]`, right? But `heap[0] = heap.pop(-1)` causes it to become `[3,2]`,.. Or is that what you want? Please clarify. – Kevin Sep 12 '17 at 19:48
  • A single `if` statement is not a cost you should be worrying about. – user2357112 Sep 12 '17 at 19:50
  • Python documentation says that `list.pop()`, no argument, removes and returns the last item in the list. – quamrana Sep 12 '17 at 19:50
  • Are you sure you understand your requirements? `heap[0] = heap.pop(-1)` sounds like the kind of thing that would appear in a heap-pop routine immediately before the sift-down, but if you're popping the only element from a heap, you shouldn't be performing this part of the procedure at all; you should just remove and return the single element. – user2357112 Sep 12 '17 at 19:52
  • @user2357112 yes it's before sift-down. You've just saved me from another debugging. So I might use the try except thing and don't bubble-down in that case. – Adam Sep 12 '17 at 19:57
  • @Adam: Just to be clear, are you aware of [the `heapq` module](https://docs.python.org/3/library/heapq.html)? Unless this is a class project that requires you to implement it yourself, I'd use `heapq` to avoid reinventing the wheel. – ShadowRanger Sep 12 '17 at 20:07
  • Actually I used the `heapq` module, but I found disappointing the lack of `decrease` function. I didn't like the workaround for this in the docs and as I'm having a Programming exam next week I wrote one. And I would do it disregarding the exam. It's a lot shorter (for what I need) and it's an object as opposed to the functions. – Adam Sep 12 '17 at 20:19
  • You can't insert an item into a list in O(1). You need another structure. Like a linked list. – dalore Feb 12 '18 at 13:02

4 Answers4

6

It sounds like you're implementing a heap, and this line is part of the implementation of the heap-pop operation. In context, it would look something like

def heappop_wrong(heap):
    popped_value = heap[0]
    heap[0] = heap.pop()  # <-- here
    sift_down(heap, 0)
    return popped_value

In that case, if the list has only one element, you shouldn't be moving the last element to the front at all. You should just remove and return the only element:

def heappop(heap):
    if len(heap) == 1:
        return heap.pop()
    popped_value = heap[0]
    heap[0] = heap.pop()
    sift_down(heap, 0)
    return popped_value

As for the cost of the if, this cost is trivial and not at all something you should be worrying about.

For moving the last element of a list to the front without replacing the old front element, this is not possible in O(1) time. You'd have to use a different data structure, like a collections.deque, or implement your own resizeable ring buffer. That's not relevant for a heap use case, though.

For moving the last element of a list to the front, stomping over the old first element if there were multiple elements and leaving the list unchanged if there was only one, an if check would probably be clearest, but again, the "leave the list unchanged if there was only one element" behavior isn't actually useful for implementing a heap-pop.

user2357112
  • 260,549
  • 28
  • 431
  • 505
  • yes, sift-down doesn't make sense if the list is empty. Moreover my sift-down implementation would give me another `IndexError` if the list would be empty. – Adam Sep 12 '17 at 20:08
  • If @ShadowRanger is really O(1), it is a solution for doing that `heap[0] = heap.pop()` anyway. – Adam Sep 12 '17 at 20:10
3

An approach that works (without exceptions, so long as the list is non-empty) is to assign to a slice of the list:

heap[:1] = (heap.pop(),)

That pops the final element and creates a length 1 tuple, which is then assigned to the heap such that it replaces the first element if it exists, or becomes the contents of the list if it's empty (as a result of the pop). It should remain O(n) because it's always replacing a single element with a single element; the higher indices are untouched.

ShadowRanger
  • 143,180
  • 12
  • 188
  • 271
  • To be clear, this is a little excessively magical. For real code, I'd probably go with something like [user235112's answer](https://stackoverflow.com/a/46184460/364696). Well, in *real* code, I'd use [the `heapq` module](https://docs.python.org/3/library/heapq.html); if you weren't aware of it already, I'd suggest taking a look. Writing your own heap as a learning exercise is fine, but don't reinvent the wheel for production code. – ShadowRanger Sep 12 '17 at 20:05
  • Actually I used the `heapq` module, but I found disappointing the lack of `decrease` function. I didn't like the workaround for this in the docs and as I'm having a Programming exam next week I wrote one. It a lot shorter (for what I need) and it's an object as opposed to the functions. – Adam Sep 12 '17 at 20:18
0

collections.deque supports removing from and appending to both the front and the back in O(1).

See https://wiki.python.org/moin/TimeComplexity.

mkrieger1
  • 19,194
  • 5
  • 54
  • 65
  • I use the list as a binary heap priority queue, so I need direct access to indeces. – Adam Sep 12 '17 at 19:51
  • You should be able to do that. It's just that *that* is O(n). You can't have it all. – mkrieger1 Sep 12 '17 at 19:57
  • From the docs: *Indexed access is O(1) at both ends but slows to O(n) in the middle. For fast random access, use lists instead.* – mkrieger1 Sep 12 '17 at 19:58
0

You can check if the list is empty before attempting pop.

if len(a) > 0:
  a.insert(0,a.pop())

By default, pop returns the last element from the list so you do not have to explicitly pass -1. And since it raises an error if the list is empty, we can check its length before attempting to pop.

But insert operation on list is O(n). For O(1) you will need to use dequeue. 

from collections import deque
a = deque()
a.append(10)
a.append(12)
if len(a) > 0:
  a.appendleft(a.pop())
print a
vaichidrewar
  • 9,251
  • 18
  • 72
  • 86