HEAP SORT .pptx
•Download as PPTX, PDF•
0 likes•241 views
The document summarizes the heap sort algorithm. It begins by defining a binary heap and its properties, such as being a complete binary tree where all levels except the last are fully filled. It then explains that heap sort works by first converting the input array into a max heap, then repeatedly removing the maximum element and sinking it down to sort the array. The key steps of the heap sort algorithm are building the max heap, swapping the root with the last element, reducing the heap size, and re-heapifying the tree after each swap.
Report
Share
More Related Content
What's hot
What's hot (20)
Similar to HEAP SORT .pptx
Similar to HEAP SORT .pptx (20)
Recently uploaded
HEAP SORT .pptx
- 1. Presentation On Heap Sort Presented by: ASGHAR ALI & TARIQ JAMIL. Presented To: Prof. Anwar Rashad.
- 2. contents • heap sort • Binary Heap • Properties of binary heap • Heap sort definition • Heapify Methods • Heap sort Algorithm
- 3. Heap sort To understand how to heap sort work. First we need to understand some basic concept related to binary heaps.
- 4. Binary heap Heap is a tree-based data structure in which all the tree nodes are in a particular order . Such that the tree satisfies the heap properties (that is a specific parent –child relationship is followed throughout The tree ). A heap data structure where the tree is complete binary tree is referred to as a binary heap .
- 5. A binary tree in which : All level except the bottom-most level are completely filled . The last level may or may not be completely filled. A complete binary tree
- 6. Properties of a binary heap 1) They are complete binary trees: This means all levels are totally filled (except maybe the last level), And the node in the last level are as left as possible . This property makes array a suitable data structure for sorting Binary heaps . We can easily calculate the indices of a nodes children ,so for parent index k, the left child will be found at the index 2*i, and the right child will be found at the index 2*i+1, (for indices that starts with 1). Similarly , for a child at the index i, its parents can be found at the index floor {(k)/2)}.
- 7. 2) Heap are mainly of two types – max heap and min heap • In max heap , the value of a node is(>=)always the value of each of the its children . • In a min heap , the value of a parent is always (<=) the value of each of its children .
- 8. 3.Root element In max heap , the elements at the root will always be maximum. In min heap, the root element will always be the smallest The heap sort algorithm takes advantages of this property to sort an array using heaps .
- 9. Heap sort Heap sort is an efficient compression-based sorting algorithm That: creates a heap from the input array. Than sorts the array taking advantages of the heap’s properties . Heap method Before going into the working of heap sort, well visualized the array as a complete binary tree. Next ,we turn it into a max heap using a process called heapification.
- 10. Cont… If all the sub trees in a binary tree are maxheaps themselves , the whole tree is a maxheap. One way the idea implement this idea would be: 1. Start at the bottom of the tree. 2. Iterate through all the nodes are we travel to the top . 3. At each step , ensure that the node and all its children from a valid max heap.
- 11. Heap Sort Algorithm Step1: Build a heap from the input data . Build a max heap to sort in increasing order and build a main heap to sort in decreasing order. Step2: Swap Root. Swap the roots elements with the last item of the heap . Step3: Reduce Heap Size : Reduce the Heap size by one 1. Step4: Re-heapify . Step5: Call Recursively : • Repeat steps 2,3,4 as long as the heap size is greater than 2.
- 12. 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 HEAPIFIED ARRAY 1 2 3 4 5 6 7 23 10 15 54 77 12 34 Next Next 77 54 10 15 23 12 34 23 10 15 54 12 77 34 23 54 10 15 77 12 34 UNSORTED ARRAY 1 2 3 4 5 6 7 23 10 12 54 15 34 77 23 10 12 54 15 34 77 77 54 23 10 15 34 12 23 54 77 10 15 34 12 23 10 77 54 15 34 12 NEXT Next
- 13. Step 6. 1 2 3 4 5 6 7 77 54 23 10 15 34 12 12 54 23 10 15 34 77 54 12 23 10 15 34 77 34 12 23 10 15 54 77 15 12 23 10 34 54 77 23 12 15 10 34 54 77 10 12 15 23 34 54 77 15 12 10 23 34 54 77 10 12 15 23 34 54 77
- 14. Algorithm for heap sort • Let ’A’ is a linear array .and ‘n’ is size of array . Heap sort (A ,n) 1) For k=n/2 to 1. [decrementation] MaxHeapify(A,n,k); calling statement [end of loop] MaxHeapify(A,n,k) 2) Set largest = k, L=2*k, & R = (2*k)+1. 3) If L <= n & A[L] > A[largest] , then set largest = L. [end of If Structure] 4) If R <= n & A[R] > A[largest] , then set largest = R. [end of If Structure] 5) If largest ≠ k , then a) interchange a[largest] , A[k] b) MaxHeapify(A,n,k) [end of If Structure] Deleting heap() 6) For k = n to 1. [decrementation] a) interchange A[1], A[k] b) MaxHeapify(A,n,1) [end of loop] 7) Exit.