Heap: Difference between revisions
No edit summary |
No edit summary |
||
| Line 10: | Line 10: | ||
* right: index x 2 + 2 | * right: index x 2 + 2 | ||
==== Insertion ==== | ==== Insertion O(log n) ==== | ||
Insert the new element at the leaves and bubble it up | Insert the new element at the leaves and bubble it up. Or, we can replace the min. element with the new element and bubble it down. | ||
==== Extract min. element ==== | ==== Extract min. element O(log n) ==== | ||
The min. element of min. Heap is the root. To remove it, swap with the bottom-most right-most element and bubble it down, swapping with the smaller element. | The min. element of min. Heap is the root. To remove it, swap with the bottom-most right-most element and bubble it down, swapping with the smaller element. | ||
Latest revision as of 05:22, 3 October 2020
A Heap is a complete binary tree. It has two forms: min. Heap and max. Heap.
In a min. Heap, the root of any sub-tree is smaller than its children. The deeper we go into the children, the bigger they are. The minimum element is the root of the heap.
In a max. Heap, the root of any-sub tree is bigger than its children. The deeper we go into the children, the smaller they are. The maximum element is the root of the heap.
A heap can be implemented in a array using a simple mapping:
- get parent: (index - 2) / 2
- left: index x 2 + 1
- right: index x 2 + 2
Insertion O(log n)
Insert the new element at the leaves and bubble it up. Or, we can replace the min. element with the new element and bubble it down.
Extract min. element O(log n)
The min. element of min. Heap is the root. To remove it, swap with the bottom-most right-most element and bubble it down, swapping with the smaller element.
Resources
| https://www.youtube.com/watch?v=oSWTXtMglKE |