Question

Hillary claims that a postorder traversal of a heap will list its keys in nonincreasing order. Draw an example of a heap that proves her wrong.

Short answer

A max-heap with postorder traversal [4, 8, 10, 7, 9] shows keys not in nonincreasing order.

Step-by-step solution

Understand Postorder Traversal

In a postorder traversal, we traverse the left subtree, then the right subtree, and finally the root node. For any node, this order is maintained.

Understand Heap Properties

A heap is a complete binary tree where each node is greater than or equal to its children (max-heap) or each node is less than or equal to its children (min-heap).

Construct a Max-Heap

Consider the following max-heap:

Perform Postorder Traversal

Perform a postorder traversal on this heap. Visit the left subtree first, followed by the right subtree, and then the root node. The correct postorder traversal is: [4, 8, 10, 7, 9]

Analyze the Result

The traversal result is: [4, 8, 10, 7, 9], which is not in nonincreasing order. This disproves that a postorder traversal of a heap will list keys in nonincreasing order.

Key concepts

heap data structure

To understand the exercise better, let's dive into the heap data structure. A heap is a specialized tree-based structure that satisfies the heap property. In a heap, each parent node is either greater than or equal to (in a max-heap) or less than or equal to (in a min-heap) its child nodes. Heaps are commonly used to implement priority queues.

• Max-Heap: The key at a parent node is always greater than or equal to the keys at its children nodes.
• Min-Heap: The key at a parent node is always less than or equal to the keys at its children nodes.

Heaps ensure that the highest (or lowest) priority element is at the root. Think of a heap as a binary tree where each level is filled, except possibly for the last level, which is filled from left to right.

complete binary tree

A complete binary tree is a type of binary tree where all levels are fully filled except possibly the last level, which is filled from left to right. This ensures the tree maximizes its use of space and maintains a balanced structure.
A complete binary tree is crucial for defining a heap because:

• It allows the heap to be efficiently represented as an array.
• Parent and child relationships can be easily determined through index calculations.

For example, if the index of a parent node is `i`, then its left child is at `2i + 1` and right child is at `2i + 2`.
Maintaining a complete binary tree helps in performing heap operations like insertion and deletion efficiently.

max-heap

In a max-heap, each node's value is greater than or equal to the values of its children. This property ensures the maximum value is always at the root node.
When analyzing a max-heap, consider the following aspects:

• Insertion: New elements are added at the end of the tree (to maintain the complete binary tree property) and then 'heapify' up to restore the max-heap property.
• Deletion: The root element is removed, and the last element is placed at the root, then 'heapify' down to restore the max-heap property.

In the context of postorder traversal, remember:

• Postorder traversal visits left subtree, right subtree, and then the root node.
• For a max-heap, this order does not guarantee nonincreasing order of keys.

The incorrect assumption that postorder traversal produces a nonincreasing order in a max-heap led to the need for the exercise, where the provided traversal disproved the claim.