Heap: Difference between revisions
Jump to navigation
Jump to search
Created page with "A Heap is a 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,..." |
No edit summary |
||
| Line 11: | Line 11: | ||
=== Insertion === | === Insertion === | ||
Insert the new element at the leaves and bubble | Insert the new element at the leaves and bubble it up. | ||
== Resources == | == Resources == | ||
Revision as of 06:57, 3 June 2018
A Heap is a 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.
Resources
| https://www.youtube.com/watch?v=oSWTXtMglKE |