Wk 3 Heaps, Priority Queues, Heapsort

Question 1

Why does a data structure exist?

Answer 1

It exists to support operations. They aren’t created in isolation.

Question 2

Does the complexity of a data structure matter? Why?

Answer 2

Yes, essentially a data structure’s operations are an algorithm to access the data

Question 3

What kind of data (dynamic or static) is best suited to a data structure?

Answer 3

Dynamic. If you’re not changing anything much, who cares how you’re storing and accessing. The concept of a data structure implies you need to operate on it.

Question 4

What are some ways to access data in a priority queue?

Answer 4

Time of Arrival (stack, queue) but could also be some key that is the priority.

Question 5

How does whether or not a list is sorted affect the insert and extract operations complexity? Which is better for which? What is the average overall.

Answer 5

A sorted list is constant extract, but linear insert.

An unsorted list is constant insert, but linear extract.

Both of these overall, assuming equal numbers of add and remove is Theta(n).

Question 6

Why would we want a lg n algorithm for a priority structure?

Answer 6

We take a hit on either the insert or delete, but overall we go to lg n. Heapsort does this.

Question 7

What op’s does heapsort support?

Answer 7

insert, extract max, delete

Question 8

When would I NOT want to use a heap?

Answer 8

If we never need to extract min/max and we know we are predisposed to do more inserts or more removes. In that case, sorted/unsorted array/linked list would make sense

Question 9

What exactly is a heap. How is it implemented?

Answer 9

a heap is a binary tree, implemented as an arrary. For each node, the parent is larger than the children. Siblings have no relationship. The last level is left-filled and other levels are full.

Question 10

What is a full, complete binary tree?

Answer 10

full = every layer filled to the bottom. complete = last layer full. Heap is full, but not necessarily complete ??–i think….

Question 11

What is the height of a binary tree?

Answer 11

lg n

Question 12

How do I find the left, right, and parent of a heap implemented as an array?

Answer 12

L = 2i
R = 2i+1
P = i/2 (floor)

Question 13

How does Heapify work? How long does it take? Why does it take that long?

Answer 13

Heapify assumes left is a heap and right is a heap and that the violator is the root. It swaps the root with the greater of the children, then recurses down to fix that child recursively. This cost is lg n. In the worst case, we have to walk the entire height of the tree, which is lg n.

Question 14

How do we run extract max from a heap? How long does it take?

Answer 14

We pop the root off, since we know its the max. Then we put the last element at the root and run heapify. Taking the root is constant, and heapify takes lg n, so overall this is a lg n algorithm.

Question 15

How does heapsort compare to quicksort? What are the differences? Why do we like one versus the other?

Answer 15

Both are n lg n. The difference is that heapsort is always n lg n whereas quicksort is n^2 in the worst case. We like quicksort because it’s avg performance is better than heapsort (less constant time?) but heapsort will never worst case surprise you.

Question 16

How do we build-heap out of an array that isnt’ a heap? How long does it take to build a heap? Why does it take that long?

Answer 16

We start at n/2 (this is the first place that we have children that are actually heaps themselves, so helps with max-heapify). then work down to 1 (the root) running max-heapify along the way. This would seem to be n/2 * lg n, but its actually n. Why? Because of ammortized analysis. We do run it n/2 times. But the average over n lg n / n/2 runs is 2 lg n. The heapify of the leaves is cheap, but the heapify of the root is expensive. As we sum up actual costs of each and take the average, the answer becomes O (n).

Question 17

How does heap-sort work? What procedures does it use? What is the cost of each, what is the total cost? Why?

Answer 17

First, build a heap O(n).
Then, continually extract-max O(lg n) (with heapify after)
Total is O( n lg n)

Question 18

How does the tournament technique work to find the 2nd largest element? The third?

Answer 18

Play a tournament. You know the 2nd best is someone who lost to the first best. How many did the best beat to win? lg n. So, find largest of THOSE and you have the second largest. This is n + lg n. the third largest lost to either the first or the second. the first beat lg n. The second beat lg (lg n). So n + lg(n) + lg(n) + lg^2(n)

Question 19

What is the definition of the ith order statistic?

Answer 19

The ith biggest. For example 3rd order statistic is the third biggest.

Question 20

Why don’t we have to sort the entire array to find the ith order statistic? How does partition help?

Answer 20

I can partition and count how many I have on each side. We know partition is Theta(n). We then recursively call the ith order alg on the appropriate side of the partition. Because the size of the problem gets smaller each time, as long as we have a decent partition,

Question 21

How does luck in my partitioning effect my ability to find the ith order statistic?

Answer 21

We know I can partition in Theta(n). How my partition worked will determine how much of a problem I have left. If I’m lucky, it cut the problem in half. – for a median, or the appropriate percent for an ith. If it did not, then my problem didn’t get that much smaller and eventually I’m looking at doing this n more times and the whole thing becomes n^2.

Question 22

How long does it take to find min/max? Why?

Answer 22

Theta(n). Every element must be considered.

Question 23

What is the T(n) for lucky and unlucky outcomes of partition for Select alg?

Answer 23

For an unlucky partition, it would take Theta (n^2) because it would be T(n) = T(n-1) + Theta(n) = Theta (n^2). For a lucky partition, it could be 1, since maybe we partition right no the element. For the average partition, it would be Theta (n), Since it would be T(n) = T(n/2) + Theta(n) = Theta(n)

Question 24

What if we could find the median of an arrary in Theta(n). (we can) What would that mean for quicksort?

Answer 24

Since we could find the median in linear, then partition around that median in linear, we will always know that we’ve got a good partition and we’ll never have a n^2 quicksort.

Question 25

How does finding the median of medians algorithm work? What is its complexity? What does it do for us wrt finding an ith order statistic?

Answer 25

It finds the middle element of all the middle elements by breaking into groups of 5. Well, first of all, it tells us that we’ll never be in the unlucky case. As long as we can guarantee a significant fraction on either side of the partition, our select algorithm can run in Theta(n). The complexity to run the median of the medians algorithm is linear.

Question 26

Why is even 1/10, 9/10 a decent break for a partition wrt ith order or quicksort?

Answer 26

???? Height of tree will be logarthmic?

Question 27

How does Median of Medians algorithm work?

Answer 27

Split n total elements into n/5 groups of five. Sort them via brute force and take the median of each group. Collect these medians as A’. Then recursively call it again and send the result into x as the median of medians.

Question 28

For what size of n does SELECT guarantee a worst partition of n/4 vs. 3n/4? Why’s it work this way?

Answer 28

50… Don’t know….
40 x 3/10 = 12
50 x 3/10 = 15
30 x 3/10 = 9

Question 29

Does SELECT with median of medians technique work with groups of 3? Why not

Answer 29

No, must be at least 5. Breaking into groups of 3, still leave 2/3 of problem left while only breaking one third of the smaller elements. Doesn’t take enough of the problem away. Just the way the numbers work out?????