To complete the removal of Kansas City, we must fix the heap:

• swap heap[0] where KC is with heap[4];
• the index in heap[0] is now 3, so change index in data[3] to 0;
• shrink the heap;
• swap heap[0] and heap[1];
• the indices in the heap elements we just swapped are 3 and 2, so swap the indices in data[3] and data[2];
• swap heap[1] and heap[3];
• the indicies in the heap elements we just swapped are 1 and 3, so swap the indices in data[1] and data[3].

• add an item at index 4 in the heap and the data table;
• add an item to the map;
• swap heap[4] and heap[1];
• the indices in the heap elements we just swapped are 4 and 1, so swap the indices in data[4] and data[1].

The result should be the following

• Follow Craig and Lara's suggestion to swap heap[0] and heap[4] first.
• the indices in the heap elements we just swapped are 1 and 2, so swap the indices in data[1] and data[2];
• the item we want is now at the end of the heap, so remember the information there (priority 1, index 2) and shrink the heap;
• remember the key from data[2] (Dallas), copy data[4] over data[2], shrink data, and remove Dallas from the map;
• the pointers from data and the map to the new data[2] (now NY, 1) are incorrect, so fix them by setting the index in heap[1] to 2 and mapping NY to 2;
• fix the heap ordering by swapping heap[0] with heap[1];
• the indices in the heap elements we just swapped are 1 and 2, so swap the indices in data[1] and data[2].

The result should be the following