Nothing special here. It’s just a blog post for summarising my algorithm learning course. Here are some questions related to Priority Queues.

Related knowledge: Binary Heap & Heapsort Summary - Part 1 - Binary Heap

# 1. Dynamic median

Design a data type that supports insert in logarithmic time, find-the-median in constant time, and remove-the-median in logarithmic time. If the number of keys in the data type is even, find/remove the lower median.

**Solution**: Use 2 Sorted Binary Heap

- The Max heap to store half smaller items
- No items in the Max heap are bigger than the ones in the Mean heap

- The Min heap to store the other half
- No items in the Min heap are smaller than the ones in the Max heap

- The 2 heap should be equal. That means, the number of item in each heap should be equal or maximum 1 item different than the other one.

You will need these methods

```
class Median {
int[] maxHeap;
int[] minHeap;
void balance() {...}
void insert(int) {...}
int findMedian() {...}
int removeMedian() {...}
}
```

**Find median**

- Depending on which heap containing more item, it will be the max or the mean, always the first item in the array.

**Balance**

- Depending on which heap having more items, remove the max/min from that heap
- If
`maxHeap`

has more items, remove the max from that heap - Otherwise, remove the mean from
`minHeap`

- If
- Insert that item to the other heap
- Repeat until they are balanced
- Complexity:
`logN`

**Insert**

- If the item is smaller than the median, insert to the
`maxHeap`

- Otherwise, insert to the
`minHeap`

- Balance the 2 heaps
- Complexity:
`logN`

for insert and`logN`

for balance

**Remove**

- Find the median
- Remove from the corresponding heap
- Balance
- Complexity:
`logN`

for remove and`logN`

for balance

# 2. Randomized priority queue

Describe how to add the methods `sample()`

and
`delRandom()`

to our binary heap implementation. The two methods return
a key that is chosen uniformly at random among the remaining keys, with the latter method also
removing that key. The `sample()`

method should take constant time; the
`delRandom()`

method should take logarithmic time. Do not worry about
resizing the underlying array.

- For
`sample()`

, simply pick a random item from the underlying array of the heap - For
`delRandom()`

, instead of swapping the max item with the last item- swap a random item with the last item
- remove the random item (currently the last item)
- swim the last item (which is currently in the random position)

# 3. Taxicab numbers

A taxicab number is an integer that can be expressed as the sum of two cubes of positive integers in two different ways: ${a}^{3}+{b}^{3}={c}^{3}+{d}^{3}$. For example, $\mathrm{1729}$ is the smallest taxicab number: ${9}^{3}+{\mathrm{10}}^{3}={1}^{3}+{\mathrm{12}}^{3}$.

Design an algorithm to find all taxicab numbers with `a`

, `b`

, `c`

and `d`

less than `n`

.

**Version 1**: Use time proportional to ${n}^{2}\mathrm{log}n$
and space proportional to ${n}^{2}$.

- Create a matrix like this. Each cell is the sum of the cubes of row and column value $\mathrm{m[i][j]}={i}^{3}+{j}^{3}$.
- Sort all the values in the matrix, highest to lowest, using any logarithmic time algorithm, a binary sorted heap in this case
- Pop out the items from the heap until the end
- If exists any 4 continuous equal values, that’s the taxicab number

```
| 0 1 2 3 4 5
--+-------------------------------
0 | 0 1 8 27 64 125
1 | 1 2 9 28 65 126
2 | 8 9 16 35 72 133
3 | 27 28 35 54 91 152
4 | 64 65 72 91 128 189
5 | 125 126 133 152 189 250
```

**Version 2**: Use time proportional to ${n}^{2}\mathrm{log}n$
and space proportional to $n$.

Actually, I couldn’t think of the solution for this. I checked the answers on Stackoverflow and on the internet, took me too long to understand…

Start with the above matrix. However, since half of the matrix is duplicated, we only need to care about the other half. Of course, the matrix will never be created to save memory

```
| 0 1 2 3 4 5
--+-------------------------------
0 | 0 1 8 27 64 125
1 | 2 9 28 65 126
2 | 16 35 72 133
3 | 54 91 152
4 | 128 189
5 | 250
```

Create a min heap and store the diagonal values. You can also use the max heap, simply do the reverse way.

Pop out the min value from the heap. For each value, if the current min equal to the previous min, we found the taxicab pair. Otherwise, add the value to the right of the current min to the heap and repeat there is no value left in the heap.

To illustrate it

- Starting heap
`2 16 54 128 250`

(`m[1,1],m[2,2],m[3,3],m[4,4],m[5,5]`

) - Loop
- Current heap
`2 16 54 128 250`

- prevMin:
`0`

- currMin:
`2`

(`m[1,1]`

) - Add
`9`

(`m[2,1]`

)

- Current heap
- Loop
- Current heap
`9 16 54 128 250`

- prevMin:
`2`

- currMin:
`9`

(`m[2,1]`

) - Add
`28`

(`m[3,1]`

)

- Current heap
- Loop
- Current heap
`16 28 54 128 250`

- prevMin:
`9`

- currMin:
`16`

(`m[2,2]`

) - Add
`35`

(`m[3,2]`

)

- Current heap
- Loop
- Current heap
`28 35 54 128 250`

- prevMin:
`16`

- currMin:
`28`

(`m[3,1]`

) - Add
`65`

(`m[4,1]`

)

- Current heap
- Loop
- Current heap
`35 54 65 128 250`

- prevMin:
`28`

- currMin:
`35`

(`m[3,2]`

) - Add
`72`

(`m[4,2]`

)

- Current heap
- …