ACO 101 Study Guide - Final Guide: Priority Queue, List Of Data Structures, Binary Tree
Document Summary
Lecture 28: heaps (as an implementation for priority queues) In this lecture we talk about a different type of binary tree called a heap. Heaps are an ef - cient way of implementing priority queues. We will rst review priority queues, then present the main properties of heaps, discuss their implementation using arrays and show the main operations available on the heap adt. A very useful data structure for many applications is the priority queue. A priority queue contains pairs of objects and priorities (or keys) associated with them. For example, a computing server may get jobs that it has to run, and each job may have an integer number associated with it, indicating how urgent the job is. In this case, the processing of the jobs is not done on a rst-come. Rst-served basis, but instead it is done in the order of their priorities, from the most urgent to the least urgent job.
