Heap data structure is an array that can be seen as a complete binary tree .Heap in memory allocation is array thus elements are stored at contingious memory locations it can be represented as complete binary tree,each node of the tree corresponds to an element of the array .
The tree is completely filled on all levels except possibly the lowest,which is filled from the left up to a point.
There are two kinds of binary heaps: max-heaps and min-heaps. In a max-heap, the max-heap property is that for every node i other than the root, the value of a node is at most the value of its parent. Thus, the largest element in a max-heap is stored at the root.
A min-heap is organized in the opposite way, each node is less than or equal to each of its children. Min-heaps are often used to implement priority queues.
Viewing a heap as a tree and a heap of n elements in based on a complete binary tree, its height is O (log n). Basic operations like insert, delete on heaps run in time at most proportional to the height of the tree and the take O (log n) time.
Why use a heap?
A heap can be thought of as a priority queue; the most important node will
always be at the top, and when removed, its replacement will be the most
important. This can be useful when coding algorithms that require certain
things to processed in a complete order, but when you don't want to perform
a full sort or need to know anything about the rest of the nodes. For
instance, a well-known algorithm for finding the shortest distance between
nodes in a graph, Dijkstra's Algorithm, can be optimized by using a
priority queue.
Heaps can also be used to sort data. A heap sort is O(nlogn) efficiency,
though it is not the fastest possible sorting algorithm.
Efficiency of a heap
Whenever you work with a heap, most of the time taken by the algorithm will
be in upheaping and downheaping. As it happens, the maximum number of
levels of a complete tree is log(n)+1, where n is the number of nodes in
the tree. Because upheap or downheap moves an element from one level to
another, the order of adding to or removing from a heap is O(logn), as you
can make switches only log(n) times, or one less time than the number of
levels in the tree .
Applications of HEAP Data Structures:
to overcome the Worst-Case Complexity of Quick Sort algorithm from O(n^2) to O( nlog(n) ) in Heap Sort.
find the smallest and largest element from a collection of array
In the implementation of the Priority queue in graph algorithms like Dijkstra's algorithm Prim's algorithm and Huffman encoding
Happy Coding ðŸ˜Š
By Programmers Army
Contributed by: Parakh Pratap Singh