Quick Overview of Heaps: Implementation and Properties
The tutorial covers the basics of heaps, focusing on their implementation using arrays and key properties such as Heap-Order Property and Complete Binary Tree Property. It also includes multiple-choice questions to test understanding. Learn about the efficient use of heaps for insertions, removals, and more.
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
COMP 352 SUMMER 2018 Tutorial Session 7 1
OUTLINE o Heap o Overview o MCQ o Exercices 2
HEAP QUICK OVERVIEW (1) The Heap data structure allows us to perform both insertions and removals in logarithmic time. Heap-Order Property: In a heap T, for every node v other than the root, the key stored at v is greater than or equal to the key stored at v's parent. For efficiency reasons, a heap should have as small a height as possible. A heap T should additionally satisfy a structural property: it must be complete. 3
HEAP QUICK OVERVIEW (2) Complete Binary Tree Property: A heap T with height h is a complete binary tree if levels 0,1,2, ,h 1 of T have the maximum number of nodes possible and in level h 1, all the internal nodes are to the left of the external nodes and there is at most one node with one child, which must be a left child. Another important node in a heap T, other than the root, is the last node of T, which is the right-most, deepest external node of T. A heap T storing n entries has height h = logn . 4
HEAP QUICK OVERVIEW (2) Implemented with array Father, r-child l-child see previous tutorial 5
MCQ 1 What feature of heaps allows them to be efficiently implemented using a partially filled array? Heaps are binary search trees. Heaps are complete binary trees. Heaps are full binary trees. D. Heaps contain only integer data. A. B. C. 6
MCQ 2 Which of the following statement concerning heaps is NOT true? A. A heap can be stored in a binary search tree. B. A heap can be stored in an array. C. A heap can be used to implement a priority queue. D. A heap can be used to sort data. 7
MCQ 3 Consider a max heap, represented by the array: 40, 30, 20, 10, 15, 16, 17, 8, 4. Now consider that a value 35 is inserted into this heap. After insertion, the new heap is A. 40, 30, 20, 10, 15, 16, 17, 8, 4, 35 B. 40, 35, 20, 10, 30, 16, 17, 8, 4, 15 C. 40, 30, 20, 10, 35, 16, 17, 8, 4, 15 D. 40, 35, 20, 10, 15, 16, 17, 8, 4, 30 8
MCQ4 Suppose you implement a heap (with the largest element on top) in an array. Consider the different arrays below, determine the one that cannot possibly be a heap: A. 7 6 5 4 3 2 1 B. 7 3 6 2 1 4 5 C. 7 6 4 3 5 2 1 D. 7 3 6 4 2 5 1 9
MCQ Suppose that we have implemented a priority queue by storing the items in a heap. We are now executing a reheapification downward and the out-of-place node has priority of 42. The out-of-place node 's parent has a priority of 72, and its left child has priority 52 and the node's right child has priority 62. Which statement best describes the status of the reheapification. The reheapification is done. The next step will interchange the two children of the out-of-place node. The next step will swap the out-of-place node with its parent. D. The next step will swap the out-of-place node with its left child. The next step will swap the out-of-place node with its right child. A. B. C. E. 10
EXERCISE 1 Write an efficient program for printing k smallest elements in an array. Elements in array can be in any order. For example, if given array is [1, 23, 12, 9, 30, 2, 50] and you are asked for the largest 3 elements i.e., k = 3 then your program should print 1, 2 and 9. 11
EXERCISE 2 Bill claims that a preorder traversal of a heap will list its keys in nondecreasing order. Draw an example of a heap that proves him wrong. 12
