# Source code for tryalgo.our_heap

```#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""\
A min heap

christoph dürr et jill-jênn vie - 2015-2019
"""

# snip{

[docs]
class OurHeap:
""" min heap

* heap: is the actual heap, heap[1] = index of the smallest element
* rank: inverse of heap with rank[x]=i iff heap[i]=x
* n: size of the heap

:complexity: init O(n log n), len O(1),
other operations O(log n) in expectation
and O(n) in worst case, due to the usage of a dictionary
"""
def __init__(self, items):
self.heap = [None]  # index 0 will be ignored
self.rank = {}
for x in items:
self.push(x)

def __len__(self):
return len(self.heap) - 1

[docs]
def push(self, x):
"""Insert new element x in the heap.
Assumption: x is not already in the heap"""
assert x not in self.rank
i = len(self.heap)
self.heap.append(x)    # add a new leaf
self.rank[x] = i
self.up(i)             # maintain heap order

[docs]
def pop(self):
"""Remove and return smallest element"""
root = self.heap[1]
del self.rank[root]
x = self.heap.pop()    # remove last leaf
if self:               # if heap is not empty
self.heap[1] = x    # move the last leaf
self.rank[x] = 1    # to the root
self.down(1)        # maintain heap order
return root

# snip}

# snip{ our_heap_up_down

[docs]
def up(self, i):
"""The value of heap[i] has decreased. Maintain heap invariant."""
x = self.heap[i]
while i > 1 and x < self.heap[i // 2]:
self.heap[i] = self.heap[i // 2]
self.rank[self.heap[i // 2]] = i
i //= 2
self.heap[i] = x       # insertion index found
self.rank[x] = i

[docs]
def down(self, i):
"""the value of heap[i] has increased. Maintain heap invariant."""
x = self.heap[i]
n = len(self.heap)
while True:
left = 2 * i       # climb down the tree
right = left + 1
if (right < n and self.heap[right] < x and
self.heap[right] < self.heap[left]):
self.heap[i] = self.heap[right]
self.rank[self.heap[right]] = i   # move right child up
i = right
elif left < n and self.heap[left] < x:
self.heap[i] = self.heap[left]
self.rank[self.heap[left]] = i    # move left child up
i = left
else:
self.heap[i] = x   # insertion index found
self.rank[x] = i
return

[docs]
def update(self, old, new):
"""Replace an element in the heap
"""
i = self.rank[old]     # change value at index i
del self.rank[old]
self.heap[i] = new
self.rank[new] = i
if old < new:          # maintain heap order
self.down(i)
else:
self.up(i)

# snip}
```