CS 225 Lecture Notes - Lecture 34: Binary Tree, Priority Queue, Insert Key
18 Nov 2016
School
Department
Course
Professor
Document Summary
Mp6 available, due 11/15, 11:59pm a heap is a binary tree(in which each node contains a comparable key value), with two special properties: For every node n, the value in n is greater than or equal tot he values in its children (and thus is also greater than or equal to all the values in its subtrees). The difference is that this data structure can be argued mathematically. This is also a structure that exists in memory. Heaps will be used to construct a priority queue. From the root to any leaf, there"s an increasing sequence of keys. The tree is a complete binary tree, very special. We exploit the quality of a complete tree, to create an array. This way we can do left child and right child simply because when we look for the children of the root, we can just do 2i. Otherwise we could get an off by 1 error.
