In [28]:
class BinaryHeap:
def __init__(self):
self.foobar = True
self.__heap_list = [0]
self.__current_size = 0

def size(self):
return self.__current_size

def is_empty(self):
return self.__current_size == 0

def insert(self, k):
self.__heap_list.append(k)
self.__current_size += 1
self.__perc_up(self.__current_size)

def __perc_up(self, i):
while i//2 > 0:
if self.__heap_list[i] < self.__heap_list[i//2]:
# violation of the binary heap order
self.__heap_list[i//2], self.__heap_list[i] = self.__heap_list[i], self.__heap_list[i//2]
i //= 2

def __perc_down(self, i):
while i*2 <= self.__current_size:
mc = self.__min_child(i)
if self.__heap_list[i] > self.__heap_list[mc]:
self.__heap_list[i], self.__heap_list[mc] = self.__heap_list[mc], self.__heap_list[i]

i = mc

def __min_child(self, i):
if (i*2) + 1 > self.__current_size:
return i*2
else:
# Compare  left child         right child
if self.__heap_list[i*2] < self.__heap_list[(i*2) + 1]:
return i*2
else:
return (i*2)+1

def del_min(self):
# Gets us the min priority key from the root of our tree
retval = self.__heap_list[1]

# Swap the last, low priority key from the end of our binheap to the root
#self.__heap_list[1] = self.__heap_list.pop()  # items from index "self.__current_size" is removed
self.__heap_list[1] = self.__heap_list[self.__current_size]
self.__heap_list.pop()
self.__current_size -= 1
self.__perc_down(1)  # perc down the root node

return retval

def build_heap(self, alist):
i = len(alist) // 2
self.__current_size = len(alist)
self.__heap_list = [0] + alist.copy()

while i > 0:
self.__perc_down(i)
i -= 1


## Testing our Bin Heap¶

In [9]:
bh = BinaryHeap()

In [10]:
bh.__heap_list

---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
<ipython-input-10-1e6e27ccb1db> in <module>
----> 1 bh.__heap_list

AttributeError: 'BinaryHeap' object has no attribute '__heap_list'
In [11]:
bh.build_heap([9,5,6,2,3])

In [12]:
dir(bh)

Out[12]:
['_BinaryHeap__current_size',
'_BinaryHeap__heap_list',
'_BinaryHeap__min_child',
'_BinaryHeap__perc_down',
'_BinaryHeap__perc_up',
'__class__',
'__delattr__',
'__dict__',
'__dir__',
'__doc__',
'__eq__',
'__format__',
'__ge__',
'__getattribute__',
'__gt__',
'__hash__',
'__init__',
'__init_subclass__',
'__le__',
'__lt__',
'__module__',
'__ne__',
'__new__',
'__reduce__',
'__reduce_ex__',
'__repr__',
'__setattr__',
'__sizeof__',
'__str__',
'__subclasshook__',
'__weakref__',
'build_heap',
'del_min',
'foobar',
'insert',
'is_empty',
'size']
In [13]:
bh._BinaryHeap__heap_list

Out[13]:
[0, 2, 3, 6, 5, 9]

## Random Number Test¶

In [29]:
from random import sample

In [30]:
nums = sample(range(500), k=250)

In [31]:
bh = BinaryHeap()

In [32]:
bh.build_heap(nums)


## Retrieving items from our heap¶

In [37]:
%pprint

Pretty printing has been turned OFF

In [33]:
sorted_nums = []
for i in range(bh.size()):
sorted_nums.append(bh.del_min())

In [38]:
sorted_nums

Out[38]:
[1, 2, 3, 4, 5, 19, 22, 24, 25, 31, 32, 33, 34, 35, 37, 39, 40, 41, 43, 45, 47, 53, 55, 56, 58, 59, 61, 62, 64, 66, 68, 69, 70, 72, 73, 77, 78, 79, 80, 81, 82, 85, 87, 88, 89, 90, 91, 95, 97, 99, 101, 102, 103, 106, 110, 111, 112, 115, 116, 117, 118, 119, 120, 121, 122, 123, 125, 130, 131, 132, 134, 136, 138, 141, 142, 144, 145, 150, 151, 153, 154, 156, 158, 160, 161, 162, 163, 164, 165, 167, 172, 173, 177, 178, 180, 182, 188, 192, 193, 194, 196, 197, 199, 202, 203, 204, 205, 207, 208, 216, 223, 224, 225, 226, 229, 230, 231, 233, 236, 238, 239, 242, 243, 244, 248, 249, 251, 253, 258, 260, 261, 262, 264, 265, 267, 269, 270, 271, 272, 274, 275, 276, 277, 278, 280, 282, 283, 284, 287, 288, 289, 291, 292, 294, 298, 303, 305, 307, 308, 309, 312, 313, 316, 318, 320, 321, 324, 329, 330, 331, 332, 333, 334, 335, 336, 338, 339, 343, 344, 346, 347, 349, 350, 352, 353, 354, 358, 359, 361, 363, 365, 366, 369, 372, 374, 375, 376, 377, 378, 379, 381, 383, 384, 385, 386, 387, 391, 393, 394, 396, 398, 401, 407, 410, 411, 414, 417, 418, 419, 421, 425, 426, 427, 429, 432, 434, 444, 446, 449, 450, 451, 454, 456, 458, 459, 461, 462, 466, 467, 469, 471, 472, 473, 476, 480, 484, 486, 489, 491, 496]
In [39]:
bh.size()

Out[39]:
0
In [41]:
bh.is_empty()

Out[41]:
True