Unit 3 : Heaps

Question 1

Heap Definition

Answer 1

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

Question 2

Why is a Heap known as a priority queue?

Answer 2

numbers with more priority at the top of the heap

Question 3

Describe several applications that use heaps

Answer 3

The priority of student registration

Question 4

How are heaps implemented?

Answer 4

One-Dimensional array

Question 5

Left child formula

Answer 5

Index * 2

Question 6

Right child formula

Answer 6

Index * 2 + 1

Question 7

parent formula

Answer 7

Index / 2

Question 8

Steps for inserting an item onto a heap

Answer 8

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

Question 9

Steps for deleting the minimum from a heap

Answer 9

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

Question 10

Inserting into heap average runtime

Answer 10

O ( 1 )

Question 11

Deleting minimum from heap runtime

Answer 11

average: O log n
Best: O ( 1 )

Question 12

How does the heap sort work?

Answer 12

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

Question 13

Heapsort runtime

Answer 13

O ( n log n )

Question 14

What is a skew heap?

Answer 14

Heap with an order condition but no structure condition.

Question 15

What is a skew heap used for?

Answer 15

Merging heaps

Question 16

Steps for merging two skew heaps

Answer 16

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.

Question 17

What is a binomial queue?

Answer 17

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

Question 18

What are the advantages of using a binomial queue?

Answer 18

constant insertion time of another binomial tree

Question 19

Lossy vs Lossless file compression

Answer 19

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

Question 20

Why Is Huffman encoding a “greedy algorithm”?

Answer 20

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

Question 21

Greedy Algorithm

Answer 21

Attempts to always make right in selecting the smallest two

Question 22

How is a heap array structured?

Answer 22

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

Question 23

Skew Heaps twisting process runtime

Answer 23

O log n

Question 24

How are binomial queues implemented?

Answer 24

Array of pointers to n-trees indexed by heights

Question 25

How to keep constant insertion time in binomial queues?

Answer 25

Keep binomial queue sorted by height

Question 26

Draw Binomial Queues

Answer 26

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

Question 27

Merge Binary Queues

Answer 27

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