Heaps

New in version 0.2.0.

Orders

class Order()

Abstract class: Classes who implement a heap order must inherit from this class.

Order.heapify(heap, key)

The heapify function, which should respect the heap order if a class inherits from this class.

Arguments:
  • heap (ArrayHeap) – The heap to use for the heapify operation
  • key (int) – The key of the node-triple to use for the heapify operation
Order.insert(heap, k, v)

The insert function, which should respect the heap order if a class inherits from this class.

Arguments:
  • heap (ArrayHeap) – The heap to use for the insert operation
  • k (int) – The key value to use for the new node
  • v (any) – The value to use for the new node
class MinOrder()

Min Heap order

class MaxOrder()

Max Heap order

Heap

class ArrayHeap(array, order)

Heap class backed by an array

Creates a heap

Arguments:
  • array (Array) – Array to use for heap creation, should consists of {key: *, value: * } objects
  • order (Order) – Preference for a min, max or Order() instance order heap.

Warning

don’t use internal methods if you want the heap to behave stable.

ArrayHeap.insert(key, value)

Insert a new node

Arguments:
  • key (int) – key of the new node
  • value (any) – value of the new node
ArrayHeap.extract()

Extracts the greatest or smallest element of the heap depending on Order()

Returns:node – The corrospending {key: *, value: *} node

See also

ArrayHeap.buildHeap(array)

builds a new heap with the given {key: *, value: *} array.

Arguments:
  • array (Array) – The {key: *, value: *} array

Helpers

If you want to create a new heap, you can use this two helper functions, which automatically create new Order() instances for the new heap.

createMinHeap()

Creates a new minHeap

Returns:a new ArrayHeap with min first order
Return type:ArrayHeap()
createMaxHeap()

Creates a new maxHeap

Returns:a new ArrayHeap with max first order
Return type:ArrayHeap()