Heap
Max heap implementation.
This is a subclass of List.
Heap.parent(i)
Arguments:
i(int): index to compute parent for.
Returns:
- (
int) parent index ofi
Heap.left(i)
Arguments:
i(int): index to compute left child for.
Returns:
- (
int) left child index ofi
Heap.right(i)
Arguments:
i(int): index to compute right child for.
Returns:
- (
int) right child index ofi
Heap:maxHeapify(i, effectiveSize)
Restores max heap condition at the ith index.
Arguments:
i(int): index at which to restore max heap condition.effectiveSize(int): effective size of the heap (eg. number of valid elements). Optional, Default:size.
Returns:
- (
Heap) modified heap
Recursively swaps down the node at i until the max heap condition is restored at a[i].
Note: this function assumes that the binary trees rooted at left and right are max heaps but
a[i] may violate the max-heap condition.
Heap:sort()
Sorts the heap using heap sort.
Returns:
- (
Heap) sorted heap
Heap:push(key, val)
Adds an element to the heap while keeping max heap property.
Arguments:
key(number): priority to add with.val(any): element to add to heap.
Returns:
- (
Heap) modified heap
Heap:pop()
Removes and returns the max priority element from the heap.
Returns:
- (
any) removed element
Heap:peek()
{any} max priority element from the heap
Note: the element is not removed.