Data Structures and Algorithms Tutorial Problems: Part 4

### Tutorial 4

#### Heap Sort

1. What would be the
1. minimum,
2. maximum
number of elements in a heap of height h?
2. Where in a heap would I find the smallest element?
3. Is an array that is sorted in reverse order a heap?
4. Is { 23, 17, 14, 6, 13, 10, 1, 5, 7, 12 } a heap?
5. Convert the Heapify function to an iterative form.
6. How could I make a FIFO queue with a heap? Is this likely to be a practical thing to do?
7. I have k sorted lists containing a total of n elements. Give an O(nlogk) algorithm to merge these lists into a single sorted list.
Hint: Use a heap for the merge.
8. A d-ary heap has d children for each node. (An ordinary heap is a binary heap.) Show how to store a d-ary heap in an array.

#### Quick Sort

1. What is the space complexity of the "standard" recursive quicksort?
Hint: Consider the stack frames used.
2. Convert a recursive quicksort to an iterative one.
3. Suggest a simple strategy that can be used to turn any sort into a stable sort.

In-place sorting algorithms do not require any more space than that occupied by the records themselves.
1. I wish to sort a collection of items whose keys can only take the values 0 or 1. Devise an O(n) algorithm for sorting these items in place. You may use auxillary storage of constant (O(n)) size.
2. Can this approach be used to sort n records with b-bit keys in O(bn) time? Explain your answer.

#### A sort?

An integer array of n elements has a majority element if there is an element that occurs more than n/2 times in the array. For example, the array:
```[ 2,2,5,1,5,5,2,5,5 ]
```
has a majority element, but the array
```[ 2,2,5,1,5,5,1,5 ]
```
does not have a majority element. Design an alghorithm to determine whether or not an array contains a majority element and to return that element if it exists.

#### Hash Tables

1. What is the worst case performance of a hash table in which collisions are stored in linked lists attached to the primary table?
2. Could I improve this by keeping the items in the linked lists in sorted order?
3. Could I use any other auxillary structure to improve the worst case performance?
2. I have a linked list of items with very long keys, k. The hash value of each key, h(k) is stored with each item. How might I make use of the hash value to speed up a search? Will this strategy work with a search tree? If yes, under what conditions?

#### Search Trees

1. How many binary search trees can I make from the list A B C D E?
2. When inserting a new node into a red-black tree, we set its colour to red. We could have set its colour to be black without violating the "if a node is red, its children are black" property. Why was it set to red?

### Key terms

stable sort
A In a stable sort, the order of equal keys in the original is retained in the output.