Heap
Heap is a special kind of binary tree, which is filled from left to right. Due to this speciality, it can be easily represented as an array with the simple relation between parent index and child index. Another property of heap is the max/min (max heap or min heap) restriction on each subtree. Incase of max heap, parent is greater than or equal to each of the children in its subtree and vice-versa in case of min heap. This property holds true for each of the subtree.
The relation between indices (given 0-base indexing):
i = index of a node:
then, index of parent = floor(i/2)
index of left child = 2i
index of right child = 2i+1
the left one is an example of min-heap and right one is an example of max-heap
Time complexity of different operations:
insert an element - O(log n)
delete an element - O(log n)
retrieve(max/min depending on type of heap) - O(1)
build heap - O(n)