Binary Heap

Overview

A binary heap is a special kind of binary tree in which the heap ordering property is satisfied. The heap ordering property can come in one of two varieties known as the min-heap property and max-heap property. Simply stated, the min-heap property is defined by a tree structure in which the value of each node in the tree is greater than or equal to the value of its parent, with the minimum-value element at the root. Conversely, the max-heap property is defined by a tree structure in which the value of each node in the tree is less than or equal to the value of its parent, with the maximum-value element at the root. One of the most common uses of a binary heap is to implement a priority queue.

Concept

Algorithmic Complexity

Big-O

HeapsHeapifyFind MaxExtract MaxIncrease KeyInsertDeleteMerge
Binary HeapO(n)O(1)O(log(n))O(log(n))O(log(n))O(log(n))O(m+n)

Implementation

Java Implementation

Coming soon!

References

Wikipedia: Binary heap