Facebook

heaps

Operations on Binomial Heap – Decrease key

Decrease key refers to reducing the key value of any node.If we want to decrease a key in Binomial heap,we will replace the key with reduced value and will repeatedly exchange the reduced key with the parent in order to restore min-heap property.The running time to perform this operation is O(log n). Example Say we… read more »

Operations on Binomial Heap – Extract-min

In Extract-Min operation node with minimum key is deleted from the binomial heap h.The running time to extract minimum value is  O(log n).The steps followed  are : Find the root (say x) with minimum key. Delete the root. Break the binomial heap into h and h’. Perform the union operation to h and h’. Given the… read more »

Operations On Binomial Heap – Union

The union of two heaps is the merging root lists by root degree.But if we simply merge two heaps then a problem can arise.There may be a chance that we get two or more trees of same root degree.This violates the property of binomial heap.To deal with this problem we have four cases and solution… read more »

Binomial Heaps

Binomial Heaps are similar to binary heaps with additional feature of implementing binomial series as sequence of trees.The heap(Fig 1) is represented using left child right sibling pointers.It has three links per node (parent,left,right) and the roots of tree are connected using single linked list.The degrees of tree decrease from left to right. Properties of… read more »

Heapsort

The Maxheap sorts the elements in increasing order whereas Minheap sorts the element in decreasing order.To sort the heap three steps have to be followed Heapify -The process picks the largest child key and compare it to the parent key. If parent key is larger than key then heapify quits, otherwise it swaps the parent… read more »

Implementation and Merging of Heaps

Implementation Heaps of n keys can be represented by array of length n+1(Fig 2).For a node at rank i ,the left child is at rank 2i +1 and the right child is at rank  2i +2.The links between nodes are not stored explicitly. In Fig 1,heap has 7 keys i.e n =7. Array will be… read more »

Heaps

A Heap is a Binary tree(Refer http://letslearncs.com/binary-trees/) that stores keys at it’s internal nodes and satisfies two additional properties which are : Relational Property Structural Property Relational Property It follows either  Min-Heap or Max-Heap property.The  Max-Heap property says that  keys of each and every child  will be less than the key   of parent(Fig 2)whereas Min-Heap  property says that  keys of each and every child are either greater than or equal to the key of parent(Fig 1).  … read more »

Sidebar