Heaps Flashcards

1
Q

Heapsort is an ___ sort and not a ___ sort.

A

In Place: Only a constant number of array elements are stored outside the input array at any time

Stable

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

Fully binary tree

A

A binary tree in which each node is either a leaf or has degree exactly 2.

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

Complete binary tree

A

A binary tree in which all leaves are on the same level and all internal nodes have degree 2.

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

Height of a node:

A

The number of edges on the longest simple path from the node down to a leaf.

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

Level of Node:

A

The length of a path from the root to the node.

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

Height of tree

A

Height of root node.

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

A binary tree of height (depth) d has at most ___ nodes

A

2^(d+1) - 1

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

A binary tree with n nodes has height at least __.

A

lg n

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

Heap

A

A nearly complete binary tree with the following two properties:

  1. Structural property: All levels are full, except possibly the last one, which is filled from left to right.
  2. Heap Property: for any node x, Parent(x) >= x.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Max-Heapify function

A

Maintain/Restore the max-heap property.

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

Build-Max-Heap

A

Create a max-heap from an unordered array.

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

Heapsort

A

Sort an array in place.

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

Running time of Max-Heapify is

A

O(log n)

Can be written in terms of the height as being O(h)

Since height is log n.

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

Running time of BUILD-Max_Heap

A

O(n)

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

Running time of Heapsort

A

O(n log n)

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

Running time of Max-Heap-Insert

A

O(log n)

17
Q

Running time of Heap-Extract-Max

A

O(log n)

18
Q

Running time of Heap-INcrease-Key

A

O(log n)

19
Q

Running time of Heap-Maximum

A

O(1)