Data Structures and Heaps in Computer Science - Lecture 10 Overview
Explore the concept of heaps and heapsort in data structures, focusing on the binary heap data structure as an array object that resembles a nearly complete binary tree. Learn about binary tree representations, heap properties, and vertex assignments in a linear array to enhance search efficiency. Understand the distinctions between min-heaps and max-heaps and their respective heap property requirements.
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
3rd Grade College of Computer Science and Information Technology Department of Computer Science Data Structures Lecture 10 Heap & Heapsort Instructor: Ghazwan Abdulnabi Al-Ali University of Basrah, Iraq
Data Structures University of Basrah Heaps The (Binary) heap data structure is an array object that can be viewed as a nearly complete binary tree. A binary tree with n nodes and depth k is complete iff its nodes correspond to the nodes numbered from 1 to n in the full binary tree of depth k. 2
Data Structures University of Basrah 3
Data Structures University of Basrah Binary tree representations 4
Data Structures University of Basrah A heap (data structure) is a linear array that stores a nearly complete tree. Only talking about binary heaps that store binary trees. nearly complete trees: all levels except possibly the lowest one are filled the bottom level is filled from left to right up to some point Want to store trees like that to facilitate search in the tree. 5
Data Structures University of Basrah Assignment of tree vertices to array elements Very easy: root is A[1] given index i of some node, we have Parent (i ) = [i/2] Left(i ) = 2i Right(i ) = 2i + 1 Implementation straightforward: i 2i left-shift by one of bit string representing i i 2i + 1 left-shift by one plus adding a 1 to the last bit i [i/2] right-shift by one 6
Data Structures University of Basrah EX: Assignment of tree vertices to array elements 7
Data Structures University of Basrah This particular vertex numbering isn t the only requirement for the thing to be a proper heap Two kinds: min-heaps and max-heaps Both cases, values in nodes satisfy heap property max-heap with max-heap property: for every node i (other than root) A[PARENT(i )] A[i ] meaning: value of node is at most value of parent, largest value is stored at root min-heap with min-heap property: for every node i (other than root) A[PARENT(i )] A[i ] meaning: value of node is at least value of parent, smallest value is stored at root 8
Data Structures University of Basrah Max & Min Heaps Example MinHeaps MaxHeaps 9
Data Structures University of Basrah Maintains the max-heap property Inputs are an array A and an index i Assumption: sub-trees rooted in LEFT(i ) and RIGHT(i ) are proper max-heaps, but A[i ] may be smaller than its children Task of Max-Heapify is to let A[i ] float down in the max- heap below it so that heap rooted in i becomes proper max-heap 10
Data Structures University of Basrah Example MAX-Heap 10\2=5 start from node 5 i=5 11
Data Structures University of Basrah Example MAX-Heap Cont. 4 3 2 1 i= 12
Data Structures University of Basrah Example MAX-Heap Cont. i=1 13
Data Structures University of Basrah Priority queues They are different: there s no real FIFO rule anymore. A priority queue maintains set S of elements, each with a key (priority). Two kinds: max-priority queues and min-priority queues, usually implemented by max-heaps and min-heaps. Max-priority queue Operations: Insert(S, x ) inserts element x into set S Maximum(S ) returns element of S with largest key Extract-Max(S ) removes and returns element of S with largest key Increase-Key(S, x, k) increases x s key to new value k, assuming k is at least as large as x s old key Min-priority queue is used via operations: Insert, Minimum, Extract-Min, and Decrease-Key 14
Data Structures University of Basrah The Heapsort algorithm Heapsort(A) 1 Build-Max-Heap(A) 2 for i length[A] down to 2 3 do exchange A[1] A[i] 4 heap-size[A] heap-size[A] -1 5 Max-Heapify(A,1) Running time: O(n log n) (Build-Max takes O(n), and then O(n) rounds with O(log n) each). 15
Data Structures University of Basrah Heap Sort The heapsort algorithm consists of two phases: - build a heap from an arbitrary array - use the heap to sort the data 19 To sort the elements in the decreasing order, use a min heap To sort the elements in the increasing order, use a max heap 12 16 4 7 1 19 12 16 1 4 7 16
Data Structures University of Basrah Heap Sort Cont. Take out biggest 19 12 16 Move the last element to the root 1 4 7 Sorted: Array A 4 1 16 12 7 19 17
Data Structures University of Basrah Heap Sort Cont. 7 swap HEAPIFY() 12 16 1 4 Sorted: Array A 7 4 1 16 12 19 18
Data Structures University of Basrah Heap Sort Cont. 16 12 7 1 4 Sorted: Array A 4 1 16 12 7 19 19
Data Structures University of Basrah Heap Sort Cont. Take out biggest 16 Move the last element to the root 12 7 1 4 Sorted: Array A 4 1 12 7 16 19 20
Data Structures University of Basrah Heap Sort Cont. 4 12 7 1 Sorted: Array A 4 1 12 7 16 19 21
Data Structures University of Basrah Heap Sort Cont. 4 swap HEAPIFY() 12 7 1 Sorted: Array A 4 1 12 7 16 19 22
Data Structures University of Basrah Heap Sort Cont. 12 7 4 1 Sorted: Array A 12 7 4 1 16 19 23
Data Structures University of Basrah Heap Sort Cont. Take out biggest 12 Move the last element to the root 7 4 1 Sorted: Array A 7 4 1 16 19 12 24
Data Structures University of Basrah Heap Sort Cont. 1 swap 7 4 Sorted: Array A 1 7 4 16 19 12 25
Data Structures University of Basrah Heap Sort Cont. 7 4 1 Sorted: Array A 4 1 7 16 19 12 26
Data Structures University of Basrah Heap Sort Cont. Take out biggest 7 Move the last element to the root 4 1 Sorted: Array A 1 4 16 19 7 12 27
Data Structures University of Basrah Heap Sort Cont. 1 4 Sorted: Array A 4 1 16 19 7 12 28
Data Structures University of Basrah Heap Sort Cont. 1 swap HEAPIFY() 4 Sorted: Array A 4 1 16 19 7 12 29
Data Structures University of Basrah Heap Sort Cont. Take out biggest 4 Move the last element to the root 1 Sorted: Array A 1 4 16 19 7 12 30
Data Structures University of Basrah Heap Sort Cont. Take out biggest 1 Sorted: Array A 4 1 16 19 7 12 31
Data Structures University of Basrah Heap Sort Cont. Sorted: 16 1 4 7 12 19 32
Data Structures University of Basrah Thank You 33
