Note 30.2.1.
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.
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:
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.
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).
Checkpoint 30.2.1.
Checkpoint 30.2.2.
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.
