Understanding Heap Sort in Data Structures
Heap Sort, a sorting algorithm based on the concept of a heap data structure, is explained in detail. The properties of a heap, its implementation using a complete binary tree, and its application in priority queues are discussed. The process of building a heap, inserting elements, and sorting them using Heap Sort is illustrated with examples. The efficiency and comparisons of Heap Sort are highlighted, along with the methods to arrange and manipulate elements within a heap.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Heap Sort Dr. Maram Bani Younes
Heap Is a data structure that is defined by two properties: It is a complete binary tree (implemented using array representation) The values stored in a heap are partially ordered. i.e. there is a relationship between the value stored at any node and the values of its children. (Complete binary trees have all levels except the bottom filled out completely, and the bottom level has all of its nodes filled in from left to right). Heaps are often used to implement priority queues and for external sorting algorithms. There are many situations, both in real life and in computing applications, where we wish to choose the next most important from a collection of people, tasks, or objects.
Example 19 2 46 16 12 54 64 22 17 66 37 35 Heap 66 64 54 17 37 35 46 2 16 12 22 19 Sorted 2 12 16 17 19 22 35 37 46 54 64 66
( ) lg , A orithm HeapSort x n : : x 1 order .. Input x array in the range n : : Output the array in sorted ( ) 1 for = x read = val 1 1 i to n { ( ) x BuildHeap read val ( , , i x ) InsertToHe ap val } = 2 for i n downTo { ( ) ( ) , 1 x ( ) swap x i ( ) Re , 1 arrangeHea p x i . end
Heap Sort One way to build a heap is to insert the elements one at a time. Each insertion takes (lg n since the value being inserted can move at most the distance from the bottom of the tree to the top of the tree. We need to insert (n) values with cost of Heap Sort does at most ( 2(n-1)lgn) comparisons of keys in the worst case. It uses fewer than (2nlgn) comparisons to sort n elements. No extra working storage area, except for one record position is required (working in place). ) times in the worst case, ( lg ) n n .
lg ( n , , ) A orithm InsetToHea p a n x : : ; Input a array of size representi ng a heap : a x a number : : ; : Output = new heap n new size of the heap + 1 x n n ( ) child = a n = n n = parent 2 lg n n ( ) n ( ( ) a = = ) 1 1 while parent 1 ( lg O n ( { ) ( ) ) if a parent child then = 2 1 i j ( ( ) ( , a ) ) swap a = parent child child parent parent = parent 2 } else = 0 { } parent stop loop . end
lg Re array ( , representi ) A orithm arrange a n : : a Input a of size n ng a heap : : ; : Output = new heap n new size of the heap 1 = n n 1 parent = 2 child ( ) 1 while child n { lg n ( ( ) ( ) + ) 2 ( ( ) ) n + = 1 if a child a child = then = 1 1 lg O n 1 child child = 1 i n j ( ( ) ( ) ) if a child a parent then { ( ( = ) ( , a ) ) swap a parent child parent child = 2 child child } else = { } child n stop the loop . end
