Heap
Heap is a balanced binary tree with a special property of each node. There are two types of Heap; Max-Heap and Min-Heap.
Max-Heap
Every node should be higher than its children. A node with the highest value should be root.
Min-Heap
Every node should be lower than its children. A node with the lowest value should be root.
Implementation
We want to able to get Left, Right, and Parent node on a heap. It can be represented much more efficiently by using an array. Let's say that the node is at the index. To get left, 2 x index + 1. To get right, 2 x index + 2. To get parent, (index - 1) / 2.
Heapify
Heapify is the process of inserting or removing an element into the heap. It places an element to the wrong position then find the right position for it. There are two types of Heapify; Sift Up and Sift Down.
Sift Up
An element is in the wrong position as a leaf, it has to be moved upwards towards the root to find its right position.
Sift Down
An element is in the wrong position as root, it has to be moved downwards towards the leaves to find its right position.
Insert
In array, an element would be added at the very end, and then Sift Up.
Remove
In array, after removing the value of the index, move over the last element to the removed one, and then Sift Down.
Access
It is easy to get as well as you know what the index is because it is an array and ordered.
Conclusion
The time complexity of Insert and Remove is Logarithmic, O (log n). But, for Access, it would be very fast, with time complexity is Constant, O(1).