"""
Author: ALLSTON MICKEY
Contributed: OMKAR PATHAK
Created On: 11th August 2017
"""
from __future__ import division
from pygorithm.data_structures import queue
import inspect
[docs]class Heap(queue.Queue):
"""
min-heap implementation as queue
"""
[docs] @staticmethod
def parent_idx(idx):
"""
retrieve the parent
"""
return idx // 2
[docs] @staticmethod
def left_child_idx(idx):
"""
retrieve the left child
"""
return (idx * 2) + 1
[docs] @staticmethod
def right_child_idx(idx):
"""
retrieve the right child
"""
return (idx * 2) + 2
[docs] def insert(self, data):
"""
inserting an element in the heap
"""
# TODO: Fix this if we want this compatible with 2.7
super().enqueue(data)
if self.rear >= 1: # heap may need to be fixed
self.heapify_up()
[docs] def heapify_up(self):
"""
Start at the end of the tree (last enqueued item).
Compare the rear item to its parent, swap if
the parent is larger than the child (min-heap property).
Repeat until the min-heap property is met.
Best Case: O(1), item is inserted at correct position, no swaps needed
Worst Case: O(log n), item needs to be swapped throughout all levels of tree
"""
child = self.rear
parent = self.parent_idx(child)
while self.queue[child] < self.queue[self.parent_idx(child)]:
# Swap (sift up) and update child:parent relation
self.queue[child], self.queue[parent] = self.queue[parent], self.queue[child]
child = parent
parent = self.parent_idx(child)
[docs] def pop(self):
"""
Removes the lowest value element (highest priority, at root) from the heap
"""
min = super().dequeue()
if self.rear >= 1: # heap may need to be fixed
self.heapify_down()
return min
[docs] def favorite(self, parent):
"""
Determines which child has the highest priority by 3 cases
"""
left = self.left_child_idx(parent)
right = self.right_child_idx(parent)
# case 1: both nodes exist
if left <= self.rear and right <= self.rear:
if self.queue[left] <= self.queue[right]:
return left
else:
return right
# case 2: only left exists
elif left <= self.rear:
return left
# case 3: no children (if left doesn't exist, neither can the right)
else:
return None
[docs] def heapify_down(self):
"""
Select the root and sift down until min-heap property is met.
While a favorite child exists, and that child is smaller
than the parent, swap them (sift down).
Best Case: O(1), item is inserted at correct position, no swaps needed
Worst Case: O(logn), item needs to be swapped throughout all levels of tree
"""
cur = 0 # start at the root
fav = self.favorite(cur) # determine favorite child
while self.queue[fav] is not None:
if self.queue[cur] > self.queue[fav]:
# Swap (sift down) and update parent:favorite relation
fav = self.favorite(cur)
self.queue[cur], self.queue[fav] = self.queue[fav], self.queue[cur]
cur = fav
else:
return
# TODO: Is this necessary?
@staticmethod
def time_complexities():
return "[Insert & Pop] Best Case: O(1), Worst Case: O(logn)"
[docs] def get_code(self):
"""
returns the code for the current class
"""
return inspect.getsource(Heap)