Facebook

Data Structures

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 Trees

Binomial Trees are one of  the type of trees that are defined  recursively. A Binomial tree of order 0 is a single node and a binomial tree of order n has a root node whose children are roots of binomial trees of order n-1, n-2, n-3, n-4, ……3,2,1,0. Properties of Binomial Tree There are 2n nodes in… read more »

Deletion In B-Trees

In order to delete elements from B-Tree we need to ensure that their properties(Refer : http://letslearncs.com/b-trees/ does not get violated.It should remain a binary search tree and number of pointers must be according to the order and keys should be one less than the order in each and every node. Example Consider a B-tree of Fig 1.Say… read more »

B-Trees

The B-tree is a generalization of a binary search tree  in which a node can have more than two children .The B-tree is optimized for systems that read and write large blocks of data.It has following properties The data items are stored at leaves. Every node has between M/2 and M children where M is a… 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 »

Hash functions

The mapping of keys to indices of a hash table is called as hash function.It is the usually the composition of two maps: Hash Code Map – Maps keys to integers when they are not integers. Compression Map – Maps wide range of integers to size of hash table.If S is size of table then… read more »

Hashing

Hashing is a method and useful technique to implement dictionaries.This method is used to perform searching,insertion and deletion at a faster rate.A function called Hash Function is used to compute and return position of the record instead of searching with comparisons.The data is stored in array called as Hash table.The Hash Function maps keys into… read more »

Representation of Graphs

Graphs can be represented by Adjacency Matrix by Sequential Representation Linked Representation by using an adjacency list that stores neighbors of a node using linked list. Adjacency Matrix It represents which nodes are adjacent to each other i.e. which nodes have edge connecting between them. Rows and Columns are labeled by graph vertices. a is… read more »

Graphs

A graph is a collections of vertices/nodes and edges(arcs).It is like a tree structure with a difference that it does not have any parent-child relationship between nodes.Instead,any complex relationships are possible between the nodes.A Graph G(Fig 1) is defined as an ordered set (V,E),where V(G) is the set of vertices and E(G) represents the edges… read more »

Sidebar