Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
[Python][library] simple heapq implementation
# heap queue simple implementation
def heappush(heap, val):
cur = len(heap)
heap.append(val)
while cur > 0:
parent = (cur - 1) // 2
if heap[parent] <= heap[cur]: break
heap[cur], heap[parent] = heap[parent], heap[cur]
cur = parent
pass
pass
def heappop(heap):
ret = heap[0]
last = heap.pop()
size = len(heap)
if size == 0: return ret
heap[0] = last
cur = 0
while True:
ch1 = 2 * cur + 1
if ch1 >= size: return ret
ch2 = ch1 + 1
child = ch2 if ch2 < size and heap[ch2] < heap[ch1] else ch1
if heap[cur] <= heap[child]: return ret
heap[child], heap[cur] = heap[cur], heap[child]
cur = child
pass
pass
if __name__ == "__main__":
heap = []
heappush(heap, 4)
heappush(heap, 10)
heappush(heap, 1)
heappush(heap, 100)
heappush(heap, 0)
heappush(heap, 20)
while heap: print heappop(heap)
pass
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment