Unit 3 : Heaps Flashcards

1
Q

Heap Definition

A

structure property ( complete binary tree )
heap order property ( min/max heap )
each nodes children are larger than it.

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

Why is a Heap known as a priority queue?

A

numbers with more priority at the top of the heap

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

Describe several applications that use heaps

A

The priority of student registration

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

How are heaps implemented?

A

One-Dimensional array

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

Left child formula

A

Index * 2

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

Right child formula

A

Index * 2 + 1

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

parent formula

A

Index / 2

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

Steps for inserting an item onto a heap

A

Insert new node into next available slot, then percolate up until it fits in the heap.

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

Steps for deleting the minimum from a heap

A

Bring up the newest added node into the root, then percolate down the smaller child until it fits in the heap

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

Inserting into heap average runtime

A

O ( 1 )

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

Deleting minimum from heap runtime

A

average: O log n
Best: O ( 1 )

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

How does the heap sort work?

A

1) need a heap
2) initialize a standard array where the heap sort will take place
3) delete the min node from the heap, and shift that value to the end of the standard array
4) fix the heap and continue until no nodes remain
- THE RESULT IS A DESCENDING ORDER SORT

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

Heapsort runtime

A

O ( n log n )

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

What is a skew heap?

A

Heap with an order condition but no structure condition.

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

What is a skew heap used for?

A

Merging heaps

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

Steps for merging two skew heaps

A

1) Merge smaller root to right subtree of larger root
2) Merge smaller root subtree recursively
3) flag largest nodes on right paths, then twist entire tree. Do not twist flagged nodes and siblings. If a node has no sibling, do not twist.

17
Q

What is a binomial queue?

A

Heap ordered forest that supports constant O ( 1 ) insertion time of another tree

18
Q

What are the advantages of using a binomial queue?

A

constant insertion time of another binomial tree

19
Q

Lossy vs Lossless file compression

A

Lossy file: some data is lost
Lossless: No data is lost

20
Q

Why Is Huffman encoding a “greedy algorithm”?

A

The higher frequency nodes are closer to the top, ensuring they have smaller codes.

21
Q

Greedy Algorithm

A

Attempts to always make right in selecting the smallest two

22
Q

How is a heap array structured?

A

0 spot blank and 3 blank slots at the end.
nodes fill array from left to right

23
Q

Skew Heaps twisting process runtime

A

O log n

24
Q

How are binomial queues implemented?

A

Array of pointers to n-trees indexed by heights

25
Q

How to keep constant insertion time in binomial queues?

A

Keep binomial queue sorted by height

26
Q

Draw Binomial Queues

A

1) convert size to binary
2) use binary form to determine structure of forest
3) draw each tree so that each tree contains 2^h nodes where h is the height
4) use the binomial coefficient to determine how many nodes exist at each depth in the tree

27
Q

Merge Binary Queues

A

1) Find combined size and convert to binary
2) use binary form to determine structure of new forest
3) merge all trees of the same height
4) if merged trees are same size of other trees, then merge again.
5) make sure new forest corresponds to the structure determined by the binary form