Source code for pygorithm.data_structures.heap

"""
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)