May 09, 2020 ( last updated : May 10, 2020 )
Heap
Data Structure and Algorithm
https://github.com/cao-weiwei/
Priority Queue
A priority queue is an abstract data type, which has the behaviour somewhat like a queue. However, the first-out element is not the first-in element on time serial but the element with the highest priority in the queue. You can think it is a container holds priorities.
As the priority queue is an ADT, it can be implemented in many of the data structures, such as arrays, linked lists and so on. However, the most efficient ways to achieve such data type is using heap. Let’s move to the next parts to see the reasons.
Heap
A heap is a binary tree with the following conditions:
- a complete binary tree, and
- for each node in the tree, the value of parent is greater (less) than or equal to the values in its children.
Typically, heap is implemented using array and the index starting at position 1. The first element in a heap it the root which is heap[1].
Since it’s a complete binary tree, for a node at index i, its left child should be at index 2*i and the right child is at 2*i+1.
The height of heap will be logN.
Inserting a node in heap
For inserting a node into a heap, we always start the operation at the last index since we want to keep the character of making it is a complete binary tree. The process as following:
- Add a new element always at the end of the index, and then
- Compare the value of new added element with its parent (at index / 2)
- if the new greater than its parent, then swap them;
- repeat this until it hite the root of the heap
Since the height of a heap is logN, this operations’s time complexity is O(logN).
Deleting a node from heap
Always delete the first element in a heap and move the last into the first index to keep the skeleton.
- for current root node, pick the largest children and comparing with it
- if the root greater than its largest children, then STOP which means it’s a valid heap;
- else swap them and
- repeat this until it hite the end of the heap
Since the height of a heap is logN, this operations’s time complexity is O(logN).
Creating a heap
There are two ways to generate a Heap, one native way is using previous insertion method. we repeat inserting for N times and it will form a Heap as a result. However, this Top-down fashion costs O (N * logN) time which is not efficient.
Another method is call heapify, which using Bottom-up, takes linear time O(N). The idea is to generate the heap in-place from the backward determining each subtree whehter form a valid subheap . The process as following:
- first, obviously the last row of leaves must be legal heap for itself.
- Then move up, for each subtree, we use the properties to adjust the nodes to make them form a valid subheap.
Heap sort
Heapsort uses a heap to sort the objects. As we know, each time for deletion in a heap, we can get the max/min element, then for a heap contains N elements, we perform deletion for N times will get a sorted output. As deletion method take O(logN) time, heap sort runs in O(N * logN).
If you like my articles please give me a star or leave comments below, thanks!
Originally published May 09, 2020
Latest update May 10, 2020
Related posts :