Overview
A heap is a nearly complete tree with a special property named heap property, which is about the relationship between a node and its children.
The heap property depends on the heap type. There are two types of heaps: max-heaps and min-heaps. In max-heaps, the property states that any node in the tree is equal to or larger than its children, and in min-heaps, it states that any node in the tree is equal to or smaller than its children.
Binary heap
A binary heap is a heap satisfying binary tree properties, i.e., each node has at most two children.
A binary heap is typically implemented by an array. Because a binary heap is a nearly complete binary tree, given the position of a node in the array, its parent and children can be easily located. Specifically, if the node index is i, then the indexes of its parent, left and right child are floor((i - 1)/2), 2*i + 1, 2*i + 2, given that the node index starts at 0.
It takes O(n) time to build a binary heap from an unorderred array, where n is the heap size [1].