CS 225 Lecture Notes - Lecture 35: Quicksort, Priority Queue, Sorting Algorithm
21 Nov 2016
School
Department
Course
Professor
Document Summary
This image reminds us of a heap, which is one way we can implement adt priority queue, whose functions include peek and removemin, with running times insert, with running times o(logn). Proportional to the height of the data structure (min)heap: buildheap template void heap::buildheap() { for(int i = parent(size); i > 0; i--) heapifydown(i) (min)heap: buildheap. [b] [u][i] [l][d][h][e] [a][p][n][o][w][ ][ ][ ] (min)heap: buildheap. Thm: the running time of buildheap on an array of size n is o(n). This is specific to the implementation of this algorithm. This buildheap is o(n) because we aren"t going to go through the whole height every single time we call heapifydown. Another way to say the runtime is it"s the sum of the heights of all the nodes. Instead of focussing specifically on running time, we observe that the time is proportional to the sum of the heights of all of the nodes, which we denote by.
