S-111
  • Home
  • Lectures
  • Problem Sets
  • Sections
  • Syllabus
  • Schedule
  • Staff
  • Resources
  • Canvas
  • Ed Discussion
  • Gradescope

Section 23

Binary heaps and heapsort

  1. Convert the following 6-element array into a valid heap. 1

    +----+----+----+----+----+----+
|  7 | 11 |  5 | 39 | 16 | 20 |
+----+----+----+----+----+----+

  2. Suppose we have the following array of integers, and we want to sort the array using heapsort. Show the interpretation of this array as a tree. 2

    +----+----+----+----+----+----+----+
|  5 |  3 | 12 |  8 |  7 |  4 |  6 |
+----+----+----+----+----+----+----+

  3. If we want the array to be sorted in ascending order, should we create a max-heap or a min-heap? 3

  4. Sort the array using heapsort, showing the heap representation after each removal of the root. 4

Hash tables

Recall from lecture that a hash table is an efficient implementation of a data dictionary. Under certain conditions, a hash table can be a more efficient dictionary implementation than a balanced binary search tree.

  1. What is the best-case time for insertion into a hash table, using big O notation? What factors play a role in this best-case time? 5

  2. What is the best-case time for searching a hash table, using big O notation? Contrast this time to binary search trees. 6

At the heart of the hash table concept is a hash function. We use the function to map any key from a key-value pair to an integer in the range 0 to n - 1 (inclusive) where n is the pre-allocated number of hash table buckets.

  1. Describe the characteristics of a good hash function. For example, explain why the hash function h that takes a string s as a key and returns the length of s modulo n is a poor hash function. 7

Using the following hash function, construct a hash table with n = 7 that uses linear probing as a method to handle collisions. Insert the following key-value pairs: (apple, 2), (cat, 7), (anvil, 3), (boy, 0), (bag, 1), (dog, 0), (cup, 9), and (down, 6).

We define the hash function h : string → integer such that, for any string input s, h(s) produces the index of the first letter in s, modulo n (the size of the hash table). The index of the letter a is 0, b is 1, et cetera.

  1. Trace the insertion of the key-value pairs into the hash table. For each insertion, keep track of the total probe length, or total number of hash table “accesses” needed to insert an item. 8

  2. What is the worst-case time for insertion into a hash table if the hash table uses linear probing to handle collisions? 9

The following diagram of a hash table contains gray cells where an item has been removed and white cells where an item has never been inserted in that position. Occupied cells contain the key of the key-value pair that was inserted at that position.

0 aardvark
1
2 cat
3 bear
4
5 dog
6
  1. Assuming the hash table has been filled using the hash function h from the previous question and linear probing as a collision resolution method, which item in the table has been inserted incorrectly? How can we be certain? 10

  1. The following is a sequence of swaps done by the “heapify” routine in order to turn the array into a valid max-heap:

    +----+----+----+----+----+----+
|  7 | 11 |  5 | 39 | 16 | 20 |     (initial)
+----+----+----+----+----+----+
+----+----+----+----+----+----+
|  7 | 11 | 20 | 39 | 16 |  5 |     (swap 20 and 5)
+----+----+----+----+----+----+
+----+----+----+----+----+----+
|  7 | 39 | 20 | 11 | 16 |  5 |     (swap 39 and 11)
+----+----+----+----+----+----+
+----+----+----+----+----+----+
| 39 | 16 | 20 | 11 |  7 |  5 |     (swap 39 and 7, 7 and 16)
+----+----+----+----+----+----+

    ↩

  2. This array has the following tree interpretation (this is not yet a valid heap, however):

     ↩

  3. We should create a max-heap, since the first nodes removed from the heap go towards the end of the array, which we want to be the largest ones for the array to be in ascending order. ↩

  4. Here’s the heap after the heapify operation:

    Here’s the array after each heap root removal:

    +----+----+----+----+----+----+----+
| 12 |  8 |  6 |  3 |  7 |  4 |  5 |    (initial)
+----+----+----+----+----+----+----+
+----+----+----+----+----+----+----+
|  8 |  7 |  6 |  3 |  5 |  4 ! 12 |    (after removing 12)
+----+----+----+----+----+----+----+
+----+----+----+----+----+----+----+
|  7 |  5 |  6 |  3 |  4 !  8   12 |    (after removing 8)
+----+----+----+----+----+----+----+
+----+----+----+----+----+----+----+
|  6 |  5 |  4 |  3 !  7    8   12 |    (after removing 7)
+----+----+----+----+----+----+----+
+----+----+----+----+----+----+----+
|  5 |  3 |  4 !  6    7    8   12 |    (after removing 6)
+----+----+----+----+----+----+----+
+----+----+----+----+----+----+----+
|  4 |  3 !  5    6    7    8   12 |    (after removing 5)
+----+----+----+----+----+----+----+
+----+----+----+----+----+----+----+
|  3 !  4    5    6    7    8   12 |    (after removing 4)
+----+----+----+----+----+----+----+
+----+----+----+----+----+----+----+
|  3    4    5    6    7    8   12 |    (after removing 3)
+----+----+----+----+----+----+----+

    ↩

  5. Best case for hash table insertion is O(1), assuming our first “probe” in hash table results in finding an empty space. This depends largely on the quality of our hash function. ↩

  6. Best case for searching is also O(1), when our first probe in the hash table produces a bucket containing the key for which we are searching. With a binary search tree, best case is also O(1) when the root node of the tree contains the key we want. However, we are much less likely to get “lucky” in the binary tree case, since our search will always start from the root node, and only searches for the root node will give us constant time performance. With a hash table, our search will start “closer” to a key we are looking for, making it much more likely to find our target key immediately. ↩

  7. A good hash function has the property that, when given keys picked at random from the set of all possible keys, each bucket is as close to equally full as possible, in the case of separate chaining — in the case of linear probing, we aim for the property that, for any search in the hash table, the worse-case probe length is as short as possible. In essence, we want the hash function to “spread” the destinations of the key-value pairs as much as possible over the hash table.

    The proposed hash function h that uses the length of the string is a very poor hash function indeed, since it will select the same bucket for strings with the same length and neighboring buckets for strings with lengths differing by a small amount. If we had no reason to think our input strings will all be of different lengths, we could end up with poor search, insertion, and deletion performance. ↩

  8. Here’s the product of inserting the key-value pairs into the table. Each key-value pair is shown with its total probe length. The insertion of (down, 6) fails, since the hash table is full.

    0 (apple, 2) [1]
    1 (anvil, 3) [2]
    2 (cat, 7) [1]
    3 (boy, 0) [3]
    4 (bag, 1) [4]
    5 (dog, 0) [3]
    6 (cup, 9) [5]
     ↩

  9. The worst case insertion time is O(n), since the entire hash table must be searched before finding an empty bucket. Insertion into a completely full hash table could be O(n), unless the number of full buckets are stored along with the hash table to detect overflow.

    Resizing the hash table when overflow is detected is costly, since every item in the hash table must be hashed again. (However, there are more efficient hash table implementations that avoid O(n) as a worst case for resizing a hash table — check out linear dynamic hashing.) ↩

  10. The key dog has been inserted incorrectly. It should have been hashed to bucket 4; for it to end up in bucket 5, something would need to be present at bucket 4, but this bucket is white, indicating that nothing has ever been there. ↩

Last updated on July 31, 2026.