Module `pythonnds.heap`

Heap is a specialized tree-based data structure which is essentially an almost complete[1] tree that satisfies the heap property: in a max heap, for any given node C, if P is a parent node of C, then the key (the value) of P is greater than or equal to the key of C. In a min heap, the key of P is less than or equal to the key of C.[2] The node at the "top" of the heap (with no parents) is called the root node.

Classes

class MaxHeap (array: list)

Initialize a max Heap

Methods

def add(self, value: ~T) ‑> NoneType: Add element to the heap
def build(self, array: list) ‑> list: Build a min Heap
def peek(self) ‑> ~T: Look up the smallest element
def remove(self) ‑> ~T: Remove smallest element from the heap
def siftDown(self, currentIdx: int, endIdx: int, heap: list) ‑> NoneType: Sift element down to restore heap order
def siftUp(self, currentIdx: int, heap: list) ‑> NoneType: Sift element up to restore heap order
def swap(self, i: int, j: int, heap: list) ‑> NoneType: Helper method for swapping elements in the heap

class MinHeap (array: list)

Initialize a min Heap

Methods

def add(self, val: ~T) ‑> NoneType: Add element to the heap
def build(self, array: list) ‑> list: Build a min Heap
def peek(self) ‑> ~T: Look up the smallest element
def remove(self) ‑> ~T: Remove Smallest element from the heap
def siftDown(self, currentIdx: int, endIdx: int, heap: list) ‑> NoneType: Sift element down to restore heap order
def siftUp(self, currentIdx: int, heap: list) ‑> NoneType: Sift element up to restore heap order
def swap(self, i: int, j: int, heap: list) ‑> NoneType: Helper method for swapping elements in the heap