#heapify

[kiasalehi]

Ready, Set, Heapify!

A binary heap is a binary tree that

(1) Is complete - new elements must be added at the deepest level from left to right, resulting in a tree with minimal height (i.e. a height of logn where n is the number of nodes)

(2) Satisfies the heap property - for a given node, its ordering relative to its parent (greater than / less than) is maintained across the heap.

In a min heap (example above; source: http://www.algolist.net), therefore, all children are greater than their parent node, and in a max heap all children are less than their parent node.

A heap is full when every non-terminal node has two children.

Heaps are one concrete implementation of a priority queue, an abstract data structure in which each element has a priority relative to others and elements with higher priority are served before those with lower priority (and those with equal priority are served in the order they appear in the queue).

We can represent/implement a heap as an array, where the root node is the first element, followed by its children from left to right, and so on. Because the heap is a complete binary tree, each parent has exactly 2 children (except for the last one, which could have 0, 1 or 2), so there's a formula for indexing into the array and getting an element's parent or children:

parent_idx = floor((child_idx - 1) / 2) child_indices = 2*(parent_idx + 1), 2*(parent_idx + 2)

Indexing into an array is constant so this gives us O(1) lookup of children/parents.

Public API of a heap:

#peek (#peek_min / #peek_max)

#extract (#extract_min / #extract_max)

#insert / #push

Peek is O(1): you're just looking up the value of your root node, which will always be the first element in the array representing the heap.

Extraction is O(logn): to extract an element, we swap it with the element in the tail position and then heapify down accordingly, which in the worst case requires making as many swaps as their are levels in the tree (logn).

Insertion is O(logn) for the same reason - we insert the element into the tail position and heapify up until the heap property is satisfied, which could take up to logn swaps.

[consandprose]

Heaps

Aren't descriptions of heaps hard to follow? Let's see if we can do better by shamelessly taking notes from the Wikipedia page.

Binary heaps: nodes have two children (it's a binary tree).

** d-ary heaps:** May be faster in practice due to memory caching.

Shape property: all levels of the tree are filled except possibly the leaf level, which is filled from left to right. This means it's a complete binary (or d-ary) tree.

Heap property: a node dominates (is smaller/larger than, depending on the type of heap) all of its children. This doesn't mean the heap is stratified, because a c-command (aunt-niece) relationship could be out of order. It's like family trees: you're likely to be older than your nieces and nephews, but you don't have to be. But you have to be older than your sons and daughters.

One way to remember how the heap operations work is that they always make the heap satisfy the shape property first, then the heap property.

The insert and delete operations move nodes vertically in the tree, and because the height of the tree is log(n), these operations are O(log n).

Insert: You insert into the bottom, in the next empty leaf slot, and then bubble up. Bubbling up means swapping a node with its parent until it gets a parent that dominates it. (Not the first time talking about trees has sounded disturbing, won't be the last.)

Delete: When you delete, you delete the root (min or max), because that's what heaps are for. Then you take a leaf, put it at the root, and bubble down. Bubbling down means swapping a node with its child, the one that dominates it the most, until it dominates both of its children.

Create: Creating a heap naively is n insertions at O(log n) each, so O(nlogn). But you can do it in a way that converges to O(n).

Do the first half of the insert operation on every node - add leaves, but don't bubble up. This makes a binary tree that satisfies the shape property but not the heap property.

Instead of bubbling everything up the whole tree, bubble everything down the sub-tree it is the root of. Start at the leaves and work your way up. Since most subtrees are very short, this turns out to be fast. This way of turning a complete binary tree into a heap is called heapify.

Implementation

In an effort to make our lives harder, or save space or something, heaps are often implemented as arrays where you just know due to the shape property which things are parents of which. Worse, some people start this array at 0, and some start it at 1.

If your root is at 0, and you have the arbitrary node at index i, its parent is at floor((i-1)/2) and its children are at 2i + 1 and 2i + 2.

If your root is at 1, i's parent is at floor(i/2) and its children are at 2i and 2i + 1.

Our reward for dealing with this is that heapsort can operate in place on an array.

Heapsort

A O(nlogn) in-place sorting algorithm, where you put everything in a heap and peel off the min n times.