Heaps

Heaps have a particular job, and they're very good at it. They make it easy to quickly access the max or min out of a set of items.

There are some interesting problems you can solve with heaps! Take a look at our Data Structures In-Depth eBook! It has practice problems for every data structure and lots more code examples to help you learn from!

What are Heaps good for?

Heaps are useful for continuously tracking the maximum (or minimum) in a group of items. You can keep adding items to the set and still have constant, O(1) time access to the max/min item. You can also remove this "top" item from the heap. This is a logarithmic action (O(log n)) because the heap needs to then re-calculate the top item.

Dijkstra's algorithm is a very well-known use case for heaps.

What are Heaps not as good for?

Heaps have no way to access a particular element, nor do they keep track of the order in which elements were inserted. They are only really useful for finding the max/min item or a series of the top items, like, for example, the 5 smallest items.

Heap Parameters and Constraints

The Data.Heap module exposes a generic data type HeapT as the starting point for our heap. It takes two parameters: a "priority policy" and then the type contained within the heap.

data HeapT prio val

Both of these are combined for the Heap type alias.

type Heap policy item = HeapT (Prio policy item) (Val policy item)

If this seems confusing, don't worry. In practice, you'll be using simpler types.

The two main examples of priority policies are MaxPolicy and MinPolicy. These allow you to create, respectively, a max heap or a min heap by using any Ord-erable type as the value. The library has useful type aliases for exactly these cases.

type MaxHeap a = Heap MaxPolicy a
type MinHeap a = Heap MinPolicy a

You can also use a heap as an associated data type. In this case, you'll want to use one of these type aliases:

type MaxPrioHeap key val = Heap FstMaxPolicy (key, val)
type MinPrioHeap key val = Heap FstMinPolicy (key, val)

This will allow you to use tuples of keys and values with your heap operations. They'll be ordered based on the key (which must implement the Ord typeclass).

Throughout the rest of this chapter, I'll be using MaxHeap examples to keep the type signatures concise and concrete, but all the functions will work with MinHeap or any other heap you create.

How do I create a Heap?

With that out of the way, we can get to the actual initialization functions, which closely resemble the common pattern we've seen so far.

empty :: MaxHeap a
singleton :: a -> MaxHeap a
fromList :: [a] -> MaxHeap a

How do I get the size of a Heap?

Heaps have a constant time size function:

size :: MaxHeap a -> Int

How do I add elements to a Heap?

You can add elements with the insert function, as you have come to expect.

insert :: a -> MaxHeap a -> MaxHeap a

How do I access Heap elements?

The primary function for accessing elements in a heap is viewHead. This allows you to see the "top" item in the heap, whether it be the maximum or minimum. This function returns a Maybe value, since the heap could be empty.

viewHead :: MaxHeap a -> Maybe a

There is also the more general view function. This returns a tuple containing the first element and, as its second element, the "remainder" of the heap if the top element is removed. Again, this is wrapped in Maybe to account for the empty heap case.

view :: MaxHeap a -> Maybe (a, MaxHeap a)

As with sequences and lists, it is also possible to take a certain number of elements from the heap. In this particular case, it will return the maximum (or minimum) elements from the heap, however many are requested.

take :: Int -> MaxHeap a -> [a]

Finally, heaps can return all their elements in a list, similar to other structures.

toList :: MaxHeap a -> [a]

How do I delete elements from a Heap?

As we saw above, view can de-structure a heap into its head and tail. So this is one way of removing the top element. But if you don't need the head and just want to remove it, you can just use viewTail:

viewTail :: MaxHeap a -> Maybe (MaxHeap a)

And similar to take, you can also drop the first X elements of a heap. This returns your remaining heap, rather than a list of elements.

drop :: Int -> MaxHeap a -> MaxHeap a

How do I combine Heaps?

Two or more heaps can be combined with the union and unions functions, like we've seen with other structures.

union :: MaxHeap a -> MaxHeap a -> MaxHeap a
unions :: [MaxHeap a] -> MaxHeap a

There are no functions for intersection or difference, as these operations aren't very useful with heaps.

Import Notes

Heaps don't have too many operators, so beyond the type names you can include everything as qualified.

import Data.Heap (MaxHeap)
import qualified Data.Heap as H

Conclusion

If you want to learn about more data structures in Haskell, make sure to head back to the series page!