Ch6: Heaps

Question 1

Heapsort’s running time

Answer 1

O(n lg n)

Question 2

Heapsort in-place or out-of-place?

Answer 2

Heapsort sorts in place

Question 3

Heap data structure is also an efficient…

Answer 3

priority queue

Question 4

(Binary) Heap data structure is…

Answer 4

an array object we can view as a nearly complete binary tree

Question 5

How is the heap binary tree filled?

Answer 5

It is completely filled on all levels, except possibly the lowest, where it is filled from the left up to a point

Question 6

An array object A that represents the heap has two properties: A.length is the array capacity, and…

Answer 6

A.heap-size represents how many array elements are active heap nodes

Question 7

The root node of the heap is stored in

Answer 7

A[1]

Question 8

Parent(i)

Answer 8

floor(i/2)

Question 9

Left(i)

Answer 9

2*i

Question 10

Right(i)

Answer 10

2*i + 1

Question 11

Two kinds of binary heaps

Answer 11

max-heaps and min-heaps

Question 12

max-heap property

Answer 12

For every node i other than the root, A[Parent(i)] >= A[i]

Question 13

min-heap property

Answer 13

For every node i other than the root, A[Parent(i)] <= A[i]

Question 14

The root of a max-heap is the…

Answer 14

largest element

Question 15

The root of a min-heap is the…

Answer 15

smallest element

Question 16

The height of a heap of n elements is

Answer 16

Big-Theta(lg n)

Question 17

The basic operations on heaps take ___ time because ___

Answer 17

basic heap operations take O(lg n) time because they run in time proportional to the height of the binary tree

Question 18

Purpose of Max-Heapify routine

Answer 18

Maintains the max-heap property

Question 19

Max-Heapify assumes what about the child subtrees of node i?

Answer 19

It assumes that Left(i) and Right(i) are max-heaps (but doesn’t know if node i is larger than its children or not)

Question 20

For a heap subtree of size n, how big are the child subtrees of the root node? In what case are these child subtrees at their largest relative to the overall subtree size?

Answer 20

The child subtrees have at most 2n/3 nodes. The worst case (when the child subtrees are at their largest w.r.t. the parent subtree) occurs when the bottom level of the tree is exactly half full.

Question 21

What recurrence describes the running time of Max-Heapify?

Answer 21

T(n) <= T(2n/3) + Big-Theta(1)

Question 22

What is the running time of Max-Heapify in terms of the number of nodes n? In terms of the height of the tree, h?

Answer 22

O(lg n) or O(h)

Question 23

Pseudocode for Max-Heapify

Answer 23