Heaps

 A Binary Heap is either Min Heap or Max Heap.
Min Binary Heap: the key at root must be minimum among all keys present in Binary Heap. the same property must be recursively true for all nodes in Binary Tree.
Min Binary Heap: The key at root must be maximum among all keys present in Binary Heap. the same property must be recursively true for all nodes in Binary Tree.

Binamial Heap:
Binamial Heap  is a Extention of Binary Heap that provides faster union or merge operations together with other operations provided by Binary Heap.

 Is a collection of tinomial trees.

 Binamial Tree Tree: A binomial Tree of order 0 has 1 node. A binomial Tree oder k can be constructed by taking two binomial trees of order k-1, and making one as leftmost child of other.

  Binomial Heap:
Is a set of Binomial Tree where each Binomial Tree follows Min Heap Property. and there can be at-most one Binomial Tree of any degree.
















Fibonacci Heap:
 In terms of Time Complexity, Fibonacci Heapbeats both Binary and Binomial Heaps.
 

  • Find : O(1)    - same as both
  • Delete : O(log n)  - same as both
  • Insert : O (1)   - O(lon n) in Binary , O(1) in binomial
  • Decrease-Key : O (1) - O(log n) in both
  • Merge : O (1)  :  O(m log n) or O(m+n) in Binary , O(log n) in Binomial.
Fibonacci Heap is collection of trees with min-heap or max-heap property. In Fibonacci Heap , trees can have any shape even all trees can be single nodes.

 

Leftist Tree / Leftist Heap:

In this Every node has an s-value ( or rank or distance) which is the distance to the nearest leaf. a leftist tree may be very unbalanced.

A leftist tree is a binary tree with properties:

1. Normal Min Heap Property: key(i) >= key(parent(i))

2.Heavier on Left side: dist(right(i)) <= dist(left(i)).

   Here dist(i) - is no of edges on the shortest path from node i to a leaf node in extended binary tree representaion.






 








Comments

Post a Comment

Popular posts from this blog

Tournament Tree or Winner Tree

Image
Tournament Tree or Winner Tree :  Is a form of min(max) heap which is a complete binary tree. every external node represents a player and internal node represents a winner. Winner: select the best player among N palyers , (N -1) players to be eliminated. we need minimum of (N-1) games (comparisons). Second best player: we can pick second best player in (N + log2(n-2)) comparisons.   The above tree contains 4 leaf nodes that represent players and have 3 levels 0, 1 and 2. Initially 2 games are conducted at level 2, one between 5 and 3 and another one between 7 and 8. In the next move, one more game is conducted between 5 and 8 to conclude the final winner. Overall we need 3 comparisons. For second best player we need to trace the candidates participated with final winner, that leads to 7 as second best. Uses: Tree selection sort using tournament tree.  
Read more

Linked List

Image
single linked list: 1. Node class NodeLL.java package com.nrs.ds.basic; public class NodeLL { Object value; NodeLL next; public NodeLL(Object value,NodeLL next){ this.value=value; this.next = next; } } 2. LinkedList implementation LinkedListImpl.java package com.nrs.ds.basic; public class LinkedListImpl<T> { NodeLL head; public LinkedListImpl(){ head = null; } public void add(Object value){ NodeLL newNode= new NodeLL(value,null); if(head == null){ head=newNode; }else{ newNode.next = head; head = newNode; } } public void delete(){ head = head.next; } public void display(){ NodeLL n=head; while(n != null){ System.out.println((T)n.value); n = n.next; } } ...
Read more