Description
Heap is a tree-based data structure with some special attributes embedded into it. Heap Data Structure has such characteristics;
- It is a form of Complete Binary Tree,
- It has a root node and its key is compared to the children nodes and the comparison is constantly carried out whenever a new node is aimed to be inserted.
In addition to the characteristics, the Heap can be internally implemented using Array or Priority Queues. The common practice is usually done with the Priority Queue.
Types of Heap
Heap Data Structure has mainly two types. These types correspond to how the order of the Heap is placed. Let’s have a look at the types in details;
Min Heap
The values of children are greater than or equal to the value of their parents; which indicates that parent nodes tend to have lower values than the children nodes.
Max Heap
Max Heap Tree
The values of children are less than or equal to the value of their parents; which indicates that parent nodes tend to have greater values than the children nodes.
Complexity of Heap
The Time and Space complexities are summed up into a common table given as:
Usage Areas of Heap
Heap Data Structure makes great use in the following areas:
- Heap Sort: Very efficient sorting algorithm whose time complexities are all the same O (n log n),
- Priority Queues: The Priority version of Queue benefits efficiently from the Heap Data structure that provides insertion, deletion extract maximum and decrease key operations in the O (log n) time complexity
Terminology
Heapify
Heapifying is a recursive process of turning the Heap to the Max Heap type, our algorithm will go towards the non-leaf nodes and look for the largest node in the tree and in all possibilities, raise the greater values above top contentiously.
Parent Node
Left node of the Tree the presentation in the array: (index -1) / 2;
Left Node
Left node of the Tree the presentation in the array: 2 * index + 1;
Right Node
Right node of the Tree the presentation in the array: 2 * index + 2;
Heap Sort
Heap sort is a very efficient algorithm that performs very well in sorting arrays.
Time Complexity
All the cases are O(n log n)
Space Complexity
O(1)
Heap Sort Code
You can checkout my GitHub repository @ https://github.com/tugrulaslan/BlogCodeSnippets/tree/master/SortingAlgorithms