Prev: Binary Search Trees 
What Every CMPT 225 Student Should Know About Mathematical Induction
 by Brad Bart, Simon Fraser University  
Part 1: Overview of Induction
Part 2: How Induction Relates to Computer Science
Part 3: Induction in CMPT 225

Part 3: Mathematical Induction in CMPT 225
Priority Queues A priority queue is like a regular queue in that it is a collection of keys which you may insert and remove, except that each key has a priority number associated with it: the lower the number, the higher the priority. The key with the highest priority is the next key to be removed. If you're having a tough time envisioning what's happening here, think of the following examples.
Case Study: Priority Queue Implementation Using an Array
Again, there are two “obvious” approaches:
Once again, you should pause to think about how you would implement insert and remove using each of these data structures. Also consider the efficiency of each operation. Once you have formed your answers, proceed to the implementation below. Implementation 1: Keys are stored in reversesorted order To insert is similar to the insert operation for a dynamic set using a sorted array: to keep the list in reverse order may require up to O(n) shifts. However, to remove the minimum would require no shifting (i.e., O(1)) because the minimum must be the last element of the array. void insert(int key, int priority) { // shift all A[] < priority int j = len1; while (j >= 0 && A[j].priority < priority) { A[j+1] = A[j]; j; } A[j+1] = Node(key, priority); len++; }
int remove() { return A[len].key; } Implementation 2: Keys are stored in any order In contrast with Implementation 1, this data structure has the opposite efficiency, i.e., there is a fast O(1) insert, but a slow O(n) remove. To insert, place the new key into the first unoccupied slot, just like for a dynamic set using an unsorted array. To remove requires a linear search to locate the minimum. void insert(int key, int priority) { A[len++] = Node(key, priority); }
int remove() { // linear search for position of minimum int smallest = A[0].priority; int smallestpos = 0; for (int pos = 1; pos < len; pos++) if (A[pos].priority < smallest.priority) { smallest = A[pos].priority; smallestpos = pos; } int ret = A[pos].key; A[pos] = A[len]; return ret; } Augmentation to Implementation 2: Indexing the minimum Consider what would happen if your algorithm maintained
the array index of the minimum. In other words, use a
variable It would certainly make a lot of things easier. For starters, remove would no longer have to a O(n) linear search to locate the minimum. But can the location of the minimum be easily updated
after an insert? No problem. If you add one new element
to a set, it's either smaller than the old minimum, in
which case you update Therefore, by this simple augmentation, both insert and remove will run in O(1) operations. There is a flaw in this plan and it's worth it for you to figure it out for yourself. And that means some thinking time on your own. Yes, the answer is in the next part, but you should really [seriously] resist the temptation to open the next page until you've thought it through. And I don't mean for something lame like 30 seconds! Or even 30 minutes! You don't want problems like this to pwn you. After you're convinced why the improved O(1) running times are a mirage, come back tomorrow to read the final instalment.  
Next: Tomorrow's Reading: The Final Instalment 