Ch6: Heaps Flashcards

1
Q

Heapsort’s running time

A

O(n lg n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Heapsort in-place or out-of-place?

A

Heapsort sorts in place

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Heap data structure is also an efficient…

A

priority queue

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

(Binary) Heap data structure is…

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

How is the heap binary tree filled?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

The root node of the heap is stored in

A

A[1]

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Parent(i)

A

floor(i/2)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Left(i)

A

2*i

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Right(i)

A

2*i + 1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Two kinds of binary heaps

A

max-heaps and min-heaps

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

max-heap property

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

min-heap property

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

The root of a max-heap is the…

A

largest element

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

The root of a min-heap is the…

A

smallest element

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

The height of a heap of n elements is

A

Big-Theta(lg n)

17
Q

The basic operations on heaps take ___ time because ___

A

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

18
Q

Purpose of Max-Heapify routine

A

Maintains the max-heap property

19
Q

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

A

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)

20
Q

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?

A

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.

21
Q

What recurrence describes the running time of Max-Heapify?

A

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

22
Q

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?

A

O(lg n) or O(h)

23
Q

Pseudocode for Max-Heapify

A