Note 30.2.4.
We will focus on max heaps. A min heap uses the same logic, only reverses the comparisons when comparing parents to their children.
Section 30.2 The Heap Structure
A heap is our first example of a tree-based data structure. A tree is a non-linear data structure that consists of nodes connected by edges. Each tree has a single root node at the top, and each node can have zero or more child nodes branching out below it.
This tree has a root node with the value 20. The root has two children: the left child with the value 8 and right with a value 12. The 8 node has a right child 50. The 12 node has two children: left child 6 and 14.
A heap is a special kind of tree called a binary tree, where each node has at most two children: a left child and a right child. In addition, heaps have two important properties:
-
Shape Property: A heap is a complete binary tree, meaning all levels of the tree are fully filled except possibly for the last level, which is filled from left to right.
-
Heap Property: In a max-heap, for any given node, its value is greater than or equal to the values of its children. In a min-heap, the value of a node is less than or equal to the values of its children.
Thus, a heap might look like either of the following:
The first level has one node. The next has two nodes. The last level has four nodes. All levels are completely full, so this is a valid heap. The heap property is also satisfied since each parent node is larger than its children.
The first level has one node. The next has two nodes. The last level has two nodes. The last level is not completely full, but the nodes are filled from left to right, so this is a valid heap. The heap property is also satisfied since each parent node is larger than its children.
These are both max heaps where every node must have a larger value than its children. This means that the largest value in the heap is always at the root node. A min heap is similar, but every node must have a smaller value than its children, meaning that the smallest value is at the top.
The heap shown on the left is complete because every node has two children except for the nodes at the last level which have none. The right heap is incomplete, as there are some available positions at the last level that are not filled. However, those locations are all to the right of the filled nodes, maintaining the shape property.
If there are gaps anywhere but the last level, or if the gaps in the last level are not all on the right side, the structure is not a valid heap. In the figure below, there is a gap in the middle of the last row. This would not be allowed in a heap.
The last level has a missing node on the left side, violating the shape property of heaps.
A violation of the heap property occurs when a parent node has a smaller value than one of its children (in a max-heap) or a larger value (in a min-heap).
The node with 20 has a child node with the value 30, violating the heap property of max-heaps.
Checkpoint 30.2.7.
Hint.
Draw out a heap. You do not need to put values in the nodes, just draw the structure. Each row has twice as many nodes as the previous row, until you get to the last row which may not be complete.
Checkpoint 30.2.8.
Which best describes the heap property in a max-heap?
-
For any given node, its value is greater than or equal to the values of its children.
-
For any given node, its value is less than or equal to the values of its children.
-
For any given node, its left child has a smaller value and its right child has a larger value.
-
For any given node, there will always be two children.
You have attempted of activities on this page.
