Heap: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
A Heap is a binary tree. It has two forms: min. Heap and max. Heap. | 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 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. | ||
Revision as of 05:12, 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
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.
Resources
| https://www.youtube.com/watch?v=oSWTXtMglKE |