Abstract data types: heaps and priority queues

Specification of the priority queue interface a priority queue is a structure which accepts and holds items over time, but which can return the item of "highest priority" whenever requested

Abstract data types: heaps and priority queues

	Specification of the priority queue interface
	Implementation of priority queues using sequences we can implement a priority queue using a simple sequence: add items normally, then scan for the best when requested

Abstract data types: heaps and priority queues

	Specification of the priority queue interface
	Implementation of priority queues using sequences
	Implementation of priority queues using ordered sequences slightly better: we can store items in sorted order, then just select the first (or last) item to retrieve the best

Abstract data types: heaps and priority queues

	Specification of the priority queue interface
	Implementation of priority queues using sequences
	Implementation of priority queues using ordered sequences
	Binary search and logarithmic complexity we can guess a random number between 1 and n in log n steps (using base 2 logarithms), given feedback about the relative order of the number and the guesses

Abstract data types: heaps and priority queues

	Specification of the priority queue interface
	Implementation of priority queues using sequences
	Implementation of priority queues using ordered sequences
	Binary search and logarithmic complexity
	The heap data structure by storing items in a binary tree, and putting better items higher in the tree (the heap ordering), we can store and retrieve a given item in logarithmic time

Abstract data types: heaps and priority queues

	Specification of the priority queue interface
	Implementation of priority queues using sequences
	Implementation of priority queues using ordered sequences
	Binary search and logarithmic complexity
	The heap data structure
	Insertion into the heap to insert into the heap, we simply add to the "last" position in the tree, then "bubble up" until the item reaches its natural (ordered) level

Abstract data types: heaps and priority queues

	Specification of the priority queue interface
	Implementation of priority queues using sequences
	Implementation of priority queues using ordered sequences
	Binary search and logarithmic complexity
	The heap data structure
	Insertion into the heap
	Extraction from the heap to remove from the heap, we simply take the top (best) item, then replace with the last and "bubble down" according to the ordering

Abstract data types: heaps and priority queues

	Specification of the priority queue interface
	Implementation of priority queues using sequences
	Implementation of priority queues using ordered sequences
	Binary search and logarithmic complexity
	The heap data structure
	Insertion into the heap
	Extraction from the heap
	A hierarchy of abstract data types we can see the relationships between all of these various (abstract and concrete) data structures as forming a layered hierarchy