CSE 205 Lecture Notes - Lecture 27: Binary Tree, Heapsort, Binary Search Algorithm
9 May 2018
School
Department
Course
Professor
CSE 205 – Lecture 27 – Heap and Heap Sort
• A complete binary tree
o A binary tree in which every level, except possibly the last, is completely filled,
and all nodes are as far left as possible
• Heaps
o Max-heap
▪ A complete binary tree in which each element is greater than or equal to
both of its children
o Properties of a heap:
▪ It is a complete binary tree
▪ It has constraint on the elements stored at each node
o As with binary search trees, there are many possible heap configurations for a
given set of elements
o Heap operations work for:
▪ Minheaps
▪ Maxheaps
• Keeps the largest value of a collection readily available
o Three primary operations for a Heap
▪ Add new element to the heap
▪ Find the maximum value
▪ Remove the maximum value
• Adding an Element to a Heap
o Add the element as a leaf, keeping the tree complete
o Then move the element up toward the root
▪ Exchanging positions with its parents
▪ Until the relationship among the elements is appropriate
o This will guarantee that the resulting tree will conform to the heap criteria
• Removing the Largest Element from a Heap
o We know that the largest element in a heap can be found at the root
