heaps

Operations on Binomial Heap – Decrease key

http://install4install.com

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 want to decrease 50 to 4 in binomial heap given in Fig 1.The steps further followed are given in Fig 2,3,4,5 respectively.

Screen Shot 2014-06-11 at 4.40.39 PM

Fig 1 : Binomial heap before decrease-key operation

Screen Shot 2014-06-11 at 4.42.16 PM

Fig 2 : Replace 50 by 4

 

4 and 21 are swapped in Fig 3 and 4 and  8 are swapped in Fig 4 in order to retain min-heap property.

Screen Shot 2014-06-11 at 4.43.35 PM

Fig 3 : Swap 3 and 21

Screen Shot 2014-06-11 at 4.44.46 PM

Fig 4 : Swap 4 and 8

Screen Shot 2014-06-11 at 4.45.35 PM

Fig 5 : Binomial heap after decrease-key operation

 


Short URL: http://tinyit.cc/9b8900
By Cusp2207 on June 11, 2014 | Computer Science | 1 comment
Tags:

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 binomial heap h in Fig 1.The first step is to find the root with minimum key.Node with value 1 is smallest so it is deleted and h is broken down into h and h’(Fig 2).

Screen Shot 2014-06-11 at 2.13.48 PM

Fig 1 : Binomial heap h

Fig 2 : Binomial heaps h and h'

Fig 2 : Binomial heaps h and h’

 

Perform the union operation on h and h’.

Screen Shot 2014-06-11 at 2.32.37 PM

Fig 3 : Union on h and h’

 

After the union operation on h and h’ the structure seems like as given in Fig 4

Screen Shot 2014-06-11 at 2.37.11 PM

Fig 4 : Structure after union of h and h’

 

Different cases are performed according to the situation.x points to 11,next-x points to 2,sibling[next-x] points to 3 as shown in Fig 5

Screen Shot 2014-06-11 at 2.38.52 PM

Fig 5 : Structure after union of h and h’

 

Case 1 is applied in Fig 6.x now points to 2,next-x points to 3 and sibling[next-x] points to 7.

Screen Shot 2014-06-11 at 2.43.45 PM

Fig 6 : Case 1 applied

 

Case 3 is applied to Fig 7.Trees with root 2 and 3 are of same order i.e. 1 and 2 is less than 3 so 3 becomes the child of 2.next-x will now point to 7 and sibling[next-x] will point to 4.

Screen Shot 2014-06-11 at 2.48.00 PM

Fig 7 : Case 3 applied

 

 

Case 3 is applied again in Fig 8.2 is less than 7 so 7 becomes the child of 2.next-x will now point to 4.

Screen Shot 2014-06-11 at 3.31.52 PM

Fig 8 : Case 3

 

Case 3 is applied in Fig 9 as 2<4 .So 4 becomes the child of 2.x now points to 2 and next-x points to null.Thus the process stops here.

Screen Shot 2014-06-11 at 3.41.23 PM

Fig 9 : Case 3 applied


Short URL: http://tinyit.cc/29008e

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 to these cases respectively. Referring to all figures we choose arbitrary names like :

  • x is the second node of merged heaps.
  • prev-x points to previous node of x.
  • next-x points to next node of x.
  • sibling[next-x] points to next node of next-x.
  • Bk and  B1 are Binomial Heaps of order k and 1 respectively.
  • We apply different cases according to the situation until next-x becomes nil.

Cases in union of binomial heaps

Case 1

If we merge  heaps and have a case like  x points to binomial heap of order k and next-x points to binomial heap of order 1 then ,then we need to shift our pointers towards right.x will now point to binomial heap with order 1.next-k will point to heap with root node d and prev-x will point to heap with root node b and order k.

Screen Shot 2014-06-05 at 4.01.45 PM

Fig 1 : Case 1

 

Case 2

If in union operation the heaps with root b,c,d are of same order k and x points to heap of order k and root node b,next-x points to next heap of x with same order and root node c and sibling[next-x] points to next heap of next-x again with same order and root node d then pointers shift by one. x now points to heap with root node c,next-x points heap with root d and prev-x points to heap with root b.

Screen Shot 2014-06-05 at 4.36.25 PM

Fig 2 : Case 2

 

Case 3

After the union operation,if  b,c are of same order and key[x] is less than key[next[x]] then c becomes the left child of b and x remain on pointing to b but next-z now points to points to d which was earlier pointed by sibling[next-x].

Screen Shot 2014-06-10 at 12.43.29 PM

Fig 3 : Case 3

 

Case 4

The pointer points to same binomial heaps as in case 3 except the difference that key of x is greater than key[next[x]].In this case,b becomes the child of c.c is pointed by x and d is pointed by next-x.

Screen Shot 2014-06-10 at 12.54.47 PM

Fig 4 : Case 4

 

Example

Consider two heaps h1 and h2 as given in Fig 5.The union operation has to be performed on these two heaps.h1 has binomial trees of order 0,1 and 2.h2 has binomial trees of order 0,1 and 3.At the point of union operation both the heaps are combined together but the resultant structure does not follows heap property i.e the resultant structure has binomial trees of same order.In Fig 5,two trees with root 2 and 5 are of order 0 and two trees with roots 1 and 3 are of order 1 violating the property of heaps.In order to make a structure satisfying heap properties we follow case according to the situation.The union of h1 and h2 is shown in Fig 6.

Screen Shot 2014-06-10 at 4.47.05 PM

Fig 5 : Heaps h1 and h2

Screen Shot 2014-06-11 at 9.54.02 AM

Fig 6 : Union of h1 and h2

 

 

In Fig 7,2 is less than 5 and both the trees are of same order i.e 0 so case 3 is followed in which root pointed by next-x(5) becomes the child of x(2) and pointer next-x shifts to right i.e it shifts to 1 and sibling[next-x] also shifts pointer to right i.e to 3.

Screen Shot 2014-06-10 at 5.18.04 PM

Fig 7 : Case 3 applied

 

In Fig 8,all three binomial trees pointed by x,next-x and sibling[next-x] are of same order i.e 1 so case 2 is followed in which all three pointers shift to right by one i.e x will point to 1,next-x will point to  3 and sibling[next-x] will point to 7.

Screen Shot 2014-06-10 at 5.23.56 PM

Fig 8 : Case 2 applied

 

 

In Fig 9,Case 3 is followed as root 1 is less than root 3 and their trees are of same order.Tree with root 3 becomes child of tree with root 1.

Screen Shot 2014-06-10 at 5.31.57 PM

Fig 9 : Case 3 applied

 

In Fig 10,Case 3 is followed again as root 1 is less than root 7 and their trees are of same order i.e. 2.Tree with root 1 becomes the child of tree with root 7.

Screen Shot 2014-06-10 at 5.40.50 PM

Fig 10 : Case 3 applied

 

In Fig 11,Case 3 is followed as 1 is less than 4 and their trees are of same order i.e.3.Tree with root 1 becomes the child of tree with root 4. The next-x becomes nil  and so the process of applying cases stop here.We get two binomial trees of different orders.They are of order 1 and 4 respectively.Union of heaps is done satisfying all the properties of binomial heap.

Screen Shot 2014-06-10 at 6.15.30 PM

Fig 11 : Case 3 applied

 


Short URL: http://tinyit.cc/f799fd

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 Binomial Heap

  • Each Binomial tree in the heap obey min-heap property.
  • There can be only 0 or 1 binomial trees for each order .

The root  value of every binomial tree is smaller than its children and there will be at most log n +1 binomial trees of binomial heap with n nodes.

Screen Shot 2014-06-02 at 2.35.41 PM

Fig 1 : Binomial Heap

 

Each binomial tree corresponds to one digit in binary representation of a number n.For e.g.the binary representation of 13(Fig 2) is 1101(23+22+20=8+4+1).The binomial heap will have 13 nodes with binomial trees of order 3,2 and 0 respectively.The orders came from the powers of 2. Either there will be no tree or there will one tree of each order i.e we cannot have any two trees of same order in the binomial heap.Similarly for a number like 15,the binary representation is 1111(23+22 +21 +20 =8+4+2+1).The binomial heap will have 15 nodes(Fig 4)with binomial trees of order 3,2,1,0 respectively.

Binomial Heap of 13

Screen Shot 2014-06-02 at 3.11.42 PM

Fig 2 : Binomial Heap of 13

 

Details of Binomial Heap in Fig 2

Screen Shot 2014-06-02 at 3.14.04 PM

Fig 3 : Details of Binomial Heap in Fig 2

 

Binomial Heap of 15

Screen Shot 2014-06-04 at 2.42.02 PM

Fig 3 : Binomial Heap of 15

 

Details of Binomial heap in Fig 3

Screen Shot 2014-06-04 at 2.44.42 PM

Fig 4 : Details of Binomial Heap in Fig 3

 

Representing Binomial Heaps

The nodes in the binomial heap can be represented by a structure with parent,key,degree,child and sibling attributes ( Fig 5).

Screen Shot 2014-06-05 at 3.41.10 PM

Fig 5 : Structure to represent node of Binomial Heap

 

Example

Consider the binomial heap as given in Fig 6.Say we want to represent 9(Say) then the structure would be like as given in Fig 7 or if we want represent 31 the structure would be like as given in Fig 8

Screen Shot 2014-06-05 at 3.40.58 PM

Fig 6 : Binomial Heap

 

Screen Shot 2014-06-05 at 3.44.45 PM

Fig 7 : Structure to represent node 9

Screen Shot 2014-06-05 at 3.46.12 PM

Fig 8 : Structure to represent node 31

 

Operations on Binomial Heaps

The various operations that can be performed on Binomial heaps are:

  1. Union
  2. Delete Min
  3. Decrease Key
  4. Delete
  5. Insert

 

 


Short URL: http://tinyit.cc/de9cf4
By Cusp2207 on June 4, 2014 | Computer Science, Data Structures | A comment?
Tags:

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 key with the largest child key. So that the parent  now becomes larger than its children.
  • Build Heap – Use the procedure ‘Heapify’ in a bottom-up fashion to convert an array  into a heap. The process starts from last nodes and not the leaves.
  • Heap Sort – Sorting is done by removing the max element and storing in array .The storage starts from last position and goes till first index of array.

Time Analysis

  • Build Heap Algorithm will run in O(n) time
  • There are n-1 calls to Heapify each call requires O(log n)time
  • Heap sort program combine Build Heap program and Heapify, therefore it has the running time of  O(n log n) time
  • Total time complexity: O(n log n)

Example

Given an array in Fig 1 .We need to convert it to Maxheap and sort it.

Screen Shot 2014-05-21 at 4.44.07 PM

Fig 1 : Array

 

Array is converted to heap in Fig 2

Screen Shot 2014-05-21 at 4.46.16 PM

Fig 2 : Heap

 

The further steps are illustrated through following figures

Screen Shot 2014-05-21 at 5.47.08 PM

Step 1

Screen Shot 2014-05-21 at 5.49.53 PM

Step 2

Screen Shot 2014-05-21 at 5.51.09 PM

Step 3

Screen Shot 2014-05-21 at 5.58.18 PM

Step 4

Screen Shot 2014-05-22 at 10.22.04 AM

Step 5

Screen Shot 2014-05-22 at 10.25.05 AM

Step 6

 

Screen Shot 2014-05-22 at 10.27.29 AM

Step 7

 

Screen Shot 2014-05-22 at 10.47.37 AM

Step 8

Screen Shot 2014-05-22 at 10.49.30 AM

Step 9

Screen Shot 2014-05-22 at 10.50.36 AM

Step 10

Screen Shot 2014-05-22 at 10.51.45 AM

Step 11

Screen Shot 2014-05-22 at 10.53.55 AM

Step 12

Screen Shot 2014-05-22 at 11.01.39 AM

Step 13

Screen Shot 2014-05-22 at 11.03.13 AM

Step 14

Screen Shot 2014-05-22 at 11.04.04 AM

Step 15

Screen Shot 2014-05-22 at 11.08.46 AM

Step 16

Screen Shot 2014-05-22 at 11.09.40 AM

Step 17

Screen Shot 2014-05-22 at 11.10.35 AM

Step 18

Screen Shot 2014-05-22 at 11.13.24 AM

Step 19

Screen Shot 2014-05-22 at 11.14.41 AM

Step 20

 

Screen Shot 2014-05-22 at 2.48.53 PM

Step 21


Short URL: http://tinyit.cc/020f01
By Cusp2207 on May 22, 2014 | Computer Science, Data Structures | A comment?
Tags:

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 of length  8(n+1=7+1).

 

Screen Shot 2014-05-21 at 2.56.59 PM

Fig 1 : Heap

 

Screen Shot 2014-05-21 at 4.28.59 PM

Fig 2 : Implementation of Heap

 

Merging two heaps

If two heaps are to be merged and a key(k) has to be inserted then we follow these steps :

  • A new heap is created with root node storing k and two given heaps as subtrees.
  • Perform downheap to restore  relational property of heap.

Example

Given are the two heaps h1 and h2 in Fig 3.We need to merge them and add 5 to it.

Screen Shot 2014-05-21 at 4.03.25 PM

Fig 3 : h1 and h2

 

A new heap h3  is created with root node storing 5 and h1,h2 as subtrees(Fig 4).

Screen Shot 2014-05-21 at 4.09.04 PM

Fig 4 : Merging of h1 and h2 with insertion of key 5.

 

Perform downheap operation to restore heap property(Fig 5).

Screen Shot 2014-05-21 at 4.11.38 PM

Fig 5 : Downheap operation


Short URL: http://tinyit.cc/eff0

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).

 

Screen Shot 2014-05-19 at 4.03.28 PM

Fig 1 : Maxheap

Screen Shot 2014-05-19 at 4.01.04 PM

Fig 2 : Minhea

 

Structural Property

All the levels are full except the last level which is left justified.Left justified means that the parents of terminal nodes will have left child and may/may not have right child(Fig 4).Tree in Fig 3 fails to satisfy structural property.

Screen Shot 2014-05-19 at 4.57.01 PM

Fig 3 : Incomplete Binary Tree

Screen Shot 2014-05-19 at 4.52.55 PM

Fig 4 : Left Filled Binary Tree

Height of a Heap

The height of heap is O(log n).

  • Let h be the height of heap with n keys.
  • The maximum no. of keys in heap  can be 2n.
  • Since there 2at depth i =0,1,2,3,….h-1 and at least one key at depth h,we have   1 +2 +4 + 2h-1 +1.
  • Thus n=2and height= O( log n).
  • h=O(log n).

Insertion in Heap

The insertion in Heap follows three steps :

  • Find the node(Say n) where key(k) has to be inserted.
  • Store key(k) at node(n).
  • After the insertion of new key,heap property can get violated.
  • Use Upheap technique to restore heap property.
  • The upheap technique swaps the key along with the upward path from the insertion node.
  • This method is followed until the key(k) reaches a node whose parent has a smaller/equal value to k.

 

Example

Screen Shot 2014-05-20 at 5.15.10 PM

 

 

 

 

 

 

 

 

Screen Shot 2014-05-20 at 5.18.37 PM

Fig 5 : Insert 5 at terminal node

Screen Shot 2014-05-20 at 5.23.08 PM

Fig 6: Use upheap method

 

Screen Shot 2014-05-20 at 5.26.39 PM

Fig 7 : Use upheap again

 

Removal from a Heap

  • This method removes the root i.e the minimum value from the heap.
  • The root is deleted and the last key takes the place at root node
  • Downheap technique is followed till the heap property is restored.
  • Downheap swaps key along the downward path.
  • Terminate downheap method leaf/terminal level is reached and key of parent is less than key of child.

Example

Screen Shot 2014-05-20 at 5.38.48 PM

Fig 8 : Remove Min element

Screen Shot 2014-05-20 at 5.44.56 PM

Fig 9 : Remove min element

Screen Shot 2014-05-20 at 5.46.55 PM

Fig 9 : Move 26 to root

 

 

 

 

 

 

 

 

 

 

Screen Shot 2014-05-20 at 5.49.05 PM

Fig 10 : Use downheap method

 

Screen Shot 2014-05-20 at 5.50.22 PM

Fig 11 : Use downheap

Screen Shot 2014-05-20 at 5.52.00 PM

Fig 11 : Use downheap


Short URL: http://tinyit.cc/c9d404
By Cusp2207 on May 21, 2014 | Computer Science | A comment?
Tags: