Lesson 7.1
The Heap Property
Every parent compares correctly against its own children. Siblings are unordered and the structure is not sorted, which is why maintaining it is cheap.
Lessons and exercises
A tree with a weaker ordering than a BST, which is exactly what makes it cheap to maintain. The heap property constrains parents against their own children only, so the extreme value sits at the root and nothing else is sorted.
Lesson 7.2
Array Representation
A complete binary tree stores in an array with no gaps, so parent and child indices are computed arithmetically rather than stored.
Lesson 7.3
Insertion and Extraction
Insertion appends and sifts up; extraction takes the root, moves the last element there, and sifts down. Both cost the height of the tree.
Lesson 7.4
Building and Heap Sort
Bottom-up construction costs linear time because most nodes sift only a short distance. Heap sort then extracts n times, giving n log n in place.
Need help with this topic?
Work through questions with a tutor and get help with the steps you find difficult.
Get help with this topic