President of the Heap

Heaps are tree-based computational data structures with the property that a node's value is always greater than or equal to that of its children (a.k.a. the heap property). Heaps support efficient FindMax O(1), Insertion O(lg N), and DeleteMax O(lg N) operations. Heaps are commonly used to implement priority queues. Heaps can also be used to sort numbers via the heap-sort algorithm, which inserts all the numbers into the heap and repeatedly pops off the current max.

The sprawling kingdom of North Patagonia was known for its picturesque waterfalls, neatly manicured cricket pitches, and tasty beef stew. However, the kingdom also suffered from the (admittedly well-deserved) reputation of being a land of political disfunction. In particular, the average tenure of a ruler of North Patagonia was approximately twelve days.

Unlike its neighbors, rulers in North Patagonia were never over-thrown; they were simply voted out office. In fact, North Patagonia's entire government voting structure was based on an idea that its founders had once observed on a reality television show. Instead of voting leaders into power, the citizens would simply maintain the right to vote the current ruler out of power at any time. When a leader was removed from power, they retired from politics and the next most-qualified candidate (as measured by the Standardized Ruling Qualification Test or SQRT) became the new leader. It was an orderly, although excessively dynamic, process.

Unfortunately, the preoccupation with SQRT scores had led to a rather strange power structure within the government. Each person in the government, including the president, could have up-to two people reporting to him or her. And, as expected, all of the officials insisted on getting exactly two people working for him or her. The only other constraint to this hierarchy was that a person's SQRT score must be higher than the scores of his or her underlings. Thus the entire government formed a binary tree structure with the hierarchy based on a single test score.

(The government hierarchy as organized by SQRT Score)

After a few hundred years, this structure had become so ingrained in the very functioning of government that the kingdom's chief architect redesigned the entire North Patagonian state house to reflect the hierarchy. The new state house was a single, unimaginably long, row of offices running across the capital city. At the western most end was office #0, the office of the president. To its east were offices number #1 and #2, the offices of two people reporting to the president. Following that were offices #3 and #4 (reporting to the person in office #1) and offices #5 and #6 (reporting to the person in office #2). This pattern repeated down the hall, with the person in office #N having employees in offices 2N+1 and 2N+2. Thus, as you got further down the hall, you were moving further down the bureaucratic ladder. In addition to organizing the physical offices such that their locations reflected the relative position of the official inside, the layout of the state house had the unexpected benefit of being ideal for hosting marathon office chair races down its hall.

(The Western side of the North Patagonian state house)

As one would expect, the entire functioning of the government hierarchy had evolved due to its advantages in the high-churn government of North Patagonia. In particular, the governmental structure provided orderly and efficient processes for three common scenarios:

1) Determining who was in charge (FindMax) - The current ruler is the person in government with the highest SQRT score. This naturally corresponds to the person at the top of the government hierarchy and the person in the western most office, #0.

2) Adding new officials (Insertion) - Each time a bright-eyed new bureaucrat took up the call of government, they would take the SQRT exam and be inserted into the correct level of the government. After the redesign of the state house, this process became exceedingly simple. The new official would move into the eastern-most unoccupied office (the empty office with the lowest number). They would then go pay a visit to their new boss. This visit had two goals. First, the new official would perform an official introduction. Second, the new official would, quite unsubtly, check their boss's SQRT score. If they then noticed they were mistakenly reporting to a boss with a lower SQRT score, they would point out this fact and immediate swap both roles and offices with their boss. The new boss would become the new subordinate and, grudgingly, move their office down the hall. As procedure dictated, the new official would then continue down the hall again to introduce him or herself to their new, new boss. This process of humiliating swaps continued until either the new official finally met a boss that had a higher SQRT score or they became the new president. As a result of this process the vital property of government was maintained: everybody was working for someone with a higher SQRT score.

3) Voting out the top official (DeleteMax) - When voters tired of the current president, they simply voted him or her out. This process was greatly simplified with the introduction of grocery store voter kiosks, where shoppers could simply log in and press the "impeach" button. The exiting president would give a speech on TV about what an honor it had been to serve the country and then would walk down the hall to notify his or her new replacement. By law the president would pick the replacement with highest SQRT score, which due to the structure of the government was already one of the two officials working for him or her. The new replacement would gleefully move into the president's office and then go down the hall to notify their replacement. Again a series of moves propagated down the hall with each official moving up notifying exactly one employee to take his or her place. And once again the vital hierarchy of the government remained unchanged.

North Patagonia continued to maintain this unique governmental structure for nearly four centuries, churning through thousands of presidents. The only period of relative stability was near the end when Robert the Uniquely Good at Filling In Test Bubbles managed to stay in power for over a hundred days. In addition to scoring well on the tests, Robert turned out to be a reasonably competent leader. Finally, tired of the lack of sufficient drama, the citizens eventually voted him out due to a poor showing of the North Patagonian cricket team.