COMS W3134 Lecture Notes - Lecture 19: Priority Queue, Binary Heap, Binary Tree
17 Nov 2016
School
Department
Course
Professor
Document Summary
Lecture: chapter 6: priority queue, order is different than regular queue, first thing that comes out is highest priority piece of data in the structure. The lower the number, the sooner it comes off the queue: priority queues also referred to as heaps Where the minimum values come off first. Where the maximum values come off first. Implementing min-heap: array or anything that implements list e. g. linkedlist. Insert: order n (to find fitting spot to insert) Deletemin: order 1 (to delete first object) Insert: order 1 (tack object onto end of list: deletemin: order n (iterate through list to find the min, want to get rid of o(n) cost, looking for o(logn) cost for both methods. Insertion: must maintain min heap condition and completeness, can filled in from left to right at the very bottom level, or start a new level if bottom level is full.
