Support us

to write
more tutorials

to create new

to keep sharing
free knowledge
for you

every dollar helps
Need help with a programming assignment? Get affordable programming homework help.

Binary heap

There are several types of heaps, but in the current article we are going to discuss the binary heap. For short, let's call it just "heap". It is used to implement priority queue ADT and in the heapsort algorithm. Heap is a complete binary tree, which answers to the heap property.

Complete binary tree

It is said, that binary tree is complete, if all its levels, except possibly the deepest, are complete. Thought, incomplete bottom level can't have "holes", which means that it has to be fulfilled from the very left node and up to some node in the middle. See illustrations below.

Correct example of a complete binary tree

Correct nearly complete binary tree

Incorrect case, middle level is incomplete

Incorrect case, pic. 1

Incorrect case, bottom level has a "hole"

Incorrect case, pic. 2

Height of a complete binary tree is O(log n).

Heap property

There are two possible types of binary heaps: max heap and min heap. The difference is that root of a min heap contains minimal element and vice versa. Priority queue is often deal with min heaps, whereas heapsort algorithm, when sorting in ascending order, uses max heap.

Heap property for min heap

For every node in a heap, node's value is lesser or equal, than values of the children.

Min heap illustration

Heap property for max heap

For every node in a heap, node's value is greater or equal, than values of the children.

Max heap illustration

To maintain simplicity, in the articles below we consider min-heap only.

See next

Contribute to AlgoList

Liked this tutorial? Please, consider making a donation. Contribute to help us keep sharing free knowledge and write new tutorials.

Every dollar helps!

Leave a reply

Your name (optional):
Your e-mail (optional):