Heap Data Structure

Question

How traversal in a heap takes place? Consider a min heap , I think we cannot traverse it like a binary tree  ......For Example if we have to print all elements of heap   Do we need to perform delete operation on root O(1) time then perform Heapify O(lgn) and again perform delete and so on which overall takes O(N) time ?  Whether same is for search as well Plz explain...

Comments

In a binary search tree, every child on the left is smaller then the root and every child on the right is greater than root which is different in case of min/max heap.

In min-heap, root has lesser value than its children and in max-heap root has higher value than the children, hence in min-heap if you want to perform binary search from root there are two options possible or none hence traversal is different from binary search tree.

see if you want simply want to print elements you can do it directly because after all it's an array. you can run a for loop and print all the elements, but here is the twist if you want to print elements in sorted order with given unsorted array of integers then first you need apply build-max/min- function which will take O(n) time and the resultant will be a min/ max heap. Then min/max heapify after deleting root node element and swapping with last children. Then reduce heap size.

let's make it more simple with example. unsorted array A = [4,77,2,88,54,5,1] .

Now, if you want to print array simply run a for loop printf(A[i]) which will take O(n) time.

Now, if you want to print it in sorted order then you first apply build-max-heap which will take O(n) time then you will get result which may be sorted or unsorted.

for eg. after applying build-max-heap on above array you may get A = [88,54,77,4,2,5,1] which is a valid max heap but not in sorted order. one might say reverse it but still it is not sorted. Now to print sorted array create a new array. Delete root element i.e. 88 from original array and put it in the last position of new array which will give first highest number.

Here deleting root element means removing it from original array. Now swap last node n value to root, reduce heap size and now apply heapify on root element which will maintain max-heap property and will result back a max-heap. Again you delete root .... gradually you will get second hightest element on n-1 position of new array and so on. In the end your new array will be sorted.

Now to delete root element will take O(1) time applying heapify on it will take logn time. This process will go for all elements in an array so eventually it will take nlogn time.

---

Build max heap takes O(n) time , suppose we are given a max heap and we need to delete all elements starting from root ( O(1)+O(lgn)  for delete and heapify) for 1 element so overall deletion would take O(n) or O(nlgn)..?

---

Build max-heap takes O(n) time                                                                                 ------------------- (I)

for n elements we need to apply (O(1)+O(logn)) for n times = O(nlogn)             -------------------(II)

Total time complexity will be T(n) = nlogn + n                                                          ------------------- (Using I and II)

nlogn > n   Hence overall complexity will be O(nlogn).

This overall procedure is of Heapsort.