algorithms-python/algorithms/heap/binary_heap.py at master · ivan1911/algorithms-python · GitHub

History

122 lines (98 loc) · 3.62 KB

Raw

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

r"""

Binary Heap. A min heap is a complete binary tree where each node is smaller than

its children. The root, therefore, is the minimum element in the tree. The min

heap uses an array to represent the data and operation. For example a min heap:

/ \

50 7

/ \ /

55 90 87

Heap [0, 4, 50, 7, 55, 90, 87]

Method in class: insert, remove_min

For example insert(2) in a min heap:

4 4 2

/ \ / \ / \

50 7 --> 50 2 --> 50 4

/ \ / \ / \ / \ / \ / \

55 90 87 2 55 90 87 7 55 90 87 7

For example remove_min() in a min heap:

4 87 7

/ \ / \ / \

50 7 --> 50 7 --> 50 87

/ \ / / \ / \

55 90 87 55 90 55 90

"""

from abc import ABCMeta, abstractmethod

class AbstractHeap(metaclass=ABCMeta):

"""Abstract Class for Binary Heap."""

def __init__(self):

"""Pass."""

@abstractmethod

def perc_up(self, i):

"""Pass."""

@abstractmethod

def insert(self, val):

"""Pass."""

@abstractmethod

def perc_down(self, i):

"""Pass."""

@abstractmethod

def min_child(self, i):

"""Pass."""

@abstractmethod

def remove_min(self):

"""Pass."""

class BinaryHeap(AbstractHeap):

"""Binary Heap Class"""

def __init__(self):

self.current_size = 0

self.heap = [(0)]

def perc_up(self, i):

while i // 2 > 0:

if self.heap[i] < self.heap[i // 2]:

# Swap value of child with value of its parent

self.heap[i], self.heap[i//2] = self.heap[i//2], self.heap[i]

i = i // 2

def insert(self, val):

"""

Method insert always start by inserting the element at the bottom.

It inserts rightmost spot so as to maintain the complete tree property.

Then, it fixes the tree by swapping the new element with its parent,

until it finds an appropriate spot for the element. It essentially

perc_up the minimum element

Complexity: O(logN)

"""

self.heap.append(val)

self.current_size = self.current_size + 1

self.perc_up(self.current_size)

"""

Method min_child returns the index of smaller of 2 children of parent at index i

"""

def min_child(self, i):

if 2 * i + 1 > self.current_size: # No right child

return 2 * i

if self.heap[2 * i] > self.heap[2 * i + 1]:

return 2 * i + 1

return 2 * i

def perc_down(self, i):

while 2 * i < self.current_size:

min_child = self.min_child(i)

if self.heap[min_child] < self.heap[i]:

# Swap min child with parent

self.heap[min_child], self.heap[i] = self.heap[i], self.heap[min_child]

i = min_child

"""

Remove Min method removes the minimum element and swap it with the last

element in the heap( the bottommost, rightmost element). Then, it

perc_down this element, swapping it with one of its children until the

min heap property is restored

Complexity: O(logN)

"""

def remove_min(self):

ret = self.heap[1] # the smallest value at beginning

# Replace it by the last value

self.heap[1] = self.heap[self.current_size]

self.current_size = self.current_size - 1

self.heap.pop()

self.perc_down(1)

return ret

algorithms-python/algorithms/heap/binary_heap.py at master · ivan1911/algorithms-python · GitHub

Expand file tree

Breadcrumbs

binary_heap.py

Latest commit

History

Breadcrumbs

binary_heap.py

File metadata and controls