A heap is a binary tree with both a shape property and a heap property. The shape property enforces the tree to behave in a balanced way by defining each node to have two children unless the node is in the very last level. The heap property ensures that each node is less than or equal to either of its child nodes if it is a min-heap, and vice versa in case of a max-heap.
Heaps are used for constant time lookups for maximum or minimum elements. We will use a heap in the next recipe to implement our own Huffman tree.
Install the lens library for easy data manipulation:
$ cabal install lens
MinHeapmodule in a file
module MinHeap (empty, insert, deleteMin, weights) ...