CS 2150 Lecture Notes - Lecture 20: Priority Queue, Avl Tree, Binary Tree

• School: University of Virginia
• Department: Computer Science
• Course: CS 2150
• Professor: Bloomfield Aaron

Document Summary

Introduction: motivation, multiuser environment: operating system must choose which process to run on cpu, management of limited resources: limited bandwidth, but want to give best possible performance. Send traffic from highest priority queue first: priority queue adt-model c. Implementations of priority queue adt: operations: insert and deletemin (finds, returns, removes min element, unsorted list (array): insert o(!) *because double size is linear deletemin(n) must go through each: unsorted list (linked list): insert o(1) and deletemin o(n, sorted list (array): insert o(n) deletemiin o(n) Insert: now has to find where to insert quickly but shove everything else down in the array element: create new node, arrange pointers is always constant. 1: deletemin: delete first and shove everything else down. 1: sorted list (linked list): insert o(n) deletemiin o(1) Could index at 0 and start root node at 0 but math would have to be changed: from node i: left child (2*i), right child (2*i+1), parent (integer division or floor(i/2).