Binary Heap Tree, Data Structure

Data Structure Binary Tree , Heap ,Binary Heap , Binary Search Tree, minheap , maxheap,Tree in data Structure

1. HEAP Anand Ingle Data Structure

2. Definition in Data structure : Heap : A special form of complete binary tree that key value of each node is no smaller or larger than the key value of its children (if any). Types of Heap:- Max-Heap : root node has the largest value . Min-Heap : root node has the smallest value What is complete Binary Tree : A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible .

3. Max Heap

4. Min Heap

5. How is Heap represented? A Heap is a Complete Binary Tree. A heap is typically represented as array.  Representation of Heap: The root element will be at Arr[0]. Below table shows indexes of other nodes for the i th  node, i.e., Arr[i]: Arr [ i /2] Returns the parent node Arr[(2*i)+1] Returns the left child node Arr[(2*i)+2] Returns the right child node

6. 9 6 3 4 5 -1 -3 1 -7 1 2 3 4 5 6 7 8 9

7. Min Heap

8. Operations on Heap : create-heap : create an empty heap heapify : create a heap out of given array of elements find-max   or  find-min : find a maximum item of a max-heap, or a minimum item of a min-heap insert : adding a new key to the heap  delete-max  or  delete-min : removing the root node of a max- or min-heap, respectively size : return the number of items in the heap. merge  ( union ) : joining two heaps to form a valid new heap containing all the elements of both, preserving the original heaps

9. Application of Heap Heapsort : One of the best sorting methods being in-place and with no quadratic worst-case scenarios. Finding the min, max, both the min and max, median, or even the k- th largest element can be done in linear time using heaps. Priority Queue: :  Priority queues can be efficiently implemented using Binary Heap because it supports insert(), delete() and extractmax (), decreaseKey () operations in O( logn ) time. Graph algorithms like  Prim’s Algorithm  and  Dijkstra’s algorithm .

10. Thank you.......