Deleting the element from the heap
Posted on August 24, 2013
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Here we will discuss deletion of element from min heap.
Pseudocode for deletion from heap
Find the index of the element to be deleted from the heap. This takes O(n) time.(If you already have the index, please skip this step) Remove the element from the heap Move the root element to the element to be deleted location Move the last element to the first position Decrease array size by 1 Now bubble down on the array(like we did in extract min).
[Read More]Application of heap (in computer science)
Posted on August 24, 2013
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Following are applications of heap:
Heap Sort - fast way to get minimum computation
SelectionSort() with time complexity - Θ(n2) when uses heap data-structure is used as Heapsort, with time compexity nlogn. Heapsort has 2 steps
Insert all n array elements in the heap O(n) Extract min to place elements in sorted order n * O(lg n)
So, it is now close to quicksort. Priority Queue
[Read More]Building of heap
Posted on August 24, 2013
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Array Implementation of Heap
Posted on August 24, 2013
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
The parent function seems to be a bit in-correct. …
Anonymous - Apr 3, 2014
The parent function seems to be a bit in-correct. It should return i/2 if i is even.
parent(i)
{
if(i is even)
return i/2;
else
return floor(i/2);
}
Thanks mate for the correction. I have corrected it.
Array Implementation of Heap
Posted on August 24, 2013
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
We have discussed a heap as binary tree. Normal implementation of tree is via pointer, but in heap it is much more efficient to use arrays.
So, suppose we have following heap (having 9 elements) :
Now, we need array of 9 elements.
Now, we see the heap having 3 levels, level 0 as root, and level 3 which is partially filled.
Now, we start putting the elements one by one.
[Read More]Dijkstra's Shortest Path Algorithm
Posted on August 4, 2013
(Last modified on August 7, 2020)
| 6 minutes
| Kinshuk Chandra
It’s Dijkstra’s algorithm, that lets you find single-source shortest paths.
Problem
Problem - Single source shortest paths
Input -
Directed graph G=(V,E) Source vertex s Output - foreach v∈V, compute L(v)=length of a shortest s-v path in G.
Assumptions:
There is a path from vertex s to vertex v (otherwise, the path length is infinity) Edge lengths are non-negative (there are other algorithms for this called , but most famous being Bellman ford algorithm which uses dynamic programming) Example of shortest path
[Read More]Introduction to Heap
Posted on July 30, 2013
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
Definition of a heap
A heap is a data structure that contains objects which have comparable keys.
Uses of Heap
Some uses for a heap include: keeping track of employee records where the social security number is the key, network edges, events where there is a priority, etc.
Such a heap is called descending heap. In an ascending heap, on the other hand, the key value stored in a node is smaller than the keys of its children nodes.
[Read More]Heap Sort in java
Posted on January 4, 2012
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
The sorting problem
Input: Array of numbers , unsorted. Eg.
Output : Same numbers sorted in some order, say increasing order. Eg.
Heap sort Algorithm
This algorithm assumes understanding of heap - Heap - Introduction. Also, it also uses ExtractMin from Heap.
Algorithm
The essence of heap sort (in-place) is this:
Convert the array to be sorted into a heap. (see BuildHeap, it uses O(n) time) Build the sorted array back to front by repeatedly removing the minimum value in the heap (the value at position 1), putting that value into the sorted array, and rebuilding the heap with one fewer element.
[Read More]Binary heap : Introduction
Posted on January 4, 2012
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Heap : Removing the min element using BubbleDown
Posted on January 4, 2012
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
We are discussing min heap here. Extracting min from the heap is same as insertion in heap that we discussed earlier. In insertion, we used bubbling up (or sifting up) method, but in extract-min we will use bubbling down (or sifting down) method.
Pseudocode:
Copy the last value in the array to the root; Remove last element, decrease heap’s size by 1;(as we are using array) Bubble down root’s value if heap property between the nodes is violated.
[Read More]