COMP 250 Lecture Notes - Lecture 23: Heapsort, Louisiana Highway 4, United States Enrichment Corporation
3 Nov 2016
School
Department
Course
Professor
Document Summary
A heap a binary tree where every level is full except the last level, and on the last level, all the nodes are as leftmost as possible. There are two main operations: removing the minimum element, and adding elements. It"s a more general version of a queue or a stack. At the end of last class, we were told we don"t need a tree structure to represent a heap. An array allows us to index all the children and parents and gives us a simple way to manage it. The left child of a node is 2* the parent"s index, and the right child is 2*parent"s+1. The way the add and remove work is trickier, but refer to the triangle pictures. When adding an element, it is added to the lowest level, and adding it might break the heap property of the node"s being less than their children. If it does, keep bubbling/swapping it up the tree until it works.
