Heap sort Part 1
Heap meaning in English is :
- Collection of things placed, thrown, or lying on one another
- A great number, or large quantity.
The origin of heap word is:
In computer technology, this word is used in a similar fashion: One usage is Heap sort and another is heap memory.
Word Heap meaning in Heap sort is like a collection of things placed on one another but in a binary tree form 😊 where a node can have a max of 2 children. This is to maintain a balance 😊. So heap is a complete binary tree where things are placed.
This heap is of two types: Max Heap and Min Heap.
Max heap is the heap where each node’s key value is greater than or equal to its children nodes’ key values.
Min heap is the heap where each node’s key value is lesser than or equal to its children nodes’ values.
When an array is used for heap implementation, node i ‘s children will be at positions 2*i and 2*i +1.
There is another new term called Heapify is used in Heap sort. Heapify is a method of converting the binary tree to Max/Min heap.