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

Visualize Bin Heap