CPSC 319 Lecture Notes - Lecture 11: Priority Queue, The Algorithm, Kinship Terminology

• School: University of Calgary
• Department: Computer Science
• Course: CPSC 319
• Professor: Leonard Manzara

Document Summary

A max heap is a binary tree where: the value of each node is the values of its children, the tree is complete. The tree is perfectly balanced: the leaf nodes in the last level are all pushed to the left, height is < lg , the largest element is always the root node, e. g. A min heap is similar except the value of each node is the values of its children: the root contains the smallest element. Heaps are not perfectly ordered: order is maintained only through linear lines of descent, lateral lines may be out of order, e. g. Heaps are normally implemented using arrays (or vectors) Elements are stored sequentially in the array: level by level from top to bottom, and, from left to right at each level. The root node is always at position 0. The position of the left child of a node at ! is: 2! + 1, where the position is < #