PRIORITY QUEUES

Some operations for a queue

			CREATE
			ENQUEUE,  ADD
			REMOVE
			IS-EMPTY-QUEUE

For a priority queue, the REMOVE is different. An element is removed according to some criteria, such as being smallest. 

Def A heap  is a binary tree in complete binary tree in which the parents are greater than or equal to their children. 

We use heaps to represent priority queues in which the smallest element is always the one to remove. This gives us a sorting algorithm called HEAPSORT. The pseudocode for this algorithm is

	make the original list into a heap;
	repeat
		remove the smallest element
	until the heap is empty;

The heap is implemented with an array, say LIST. The children of LIST [J] are LIST [2*J] and LIST [2*J + 1]. 

Create the heap We move each parent down the heap until it is in its proper position. 

Ex Let LIST be

LIST		M	Y 	L	E	A	S	T
INDEX	1	2	3	4	5	6	7

The HEAP can be thought of as

				M

			Y		L

		E	    A	     S		T



The parents are at index 1, 2, . . . , SIZE div 2. In this case, the first three elements of LIST are parents. These elements are switched with their greater child. 

INDEX = 3	Switch L and T
INDEX = 2	No switch
INDEX = 1	Switch M and Y


LIST		Y	M	T	E	A	S	L
INDEX	1	2	3	4	5	6	7

HEAP				Y

			M		T

		E	      A         S		L

The heap is now created. 

Sort 

Pass 1 
Remove the largest element from the heap. (Exchange the first element of the list with the end of the unsorted part of the list.)

LIST		L	M	T	E	A	S	|	Y
INDEX	1	2	3	4	5	6		7

HEAP				L

			M		T

		E	      A         S		

Rebuild the heap by moving the topmost element L down to its correct position. 

LIST		T	M	L	E	A	S	|	Y
INDEX	1	2	3	4	5	6		7

HEAP				T

			M		L

		E	      A         S		

Pass 1 complete 

Pass 2 

Exchange T (the topmost element) with S (the last element in the heap). 

LIST		S	M	L	E	A	|	T	Y
INDEX	1	2	3	4	5		6	7

HEAP				S

			M		L

		E	      A     

 Rebuild the heap. In this case, nothing changes. 

Pass 2 complete 

Pass 3 

Exchange S and A. 

LIST		A	M	L	E	|	S	T	Y
INDEX	1	2	3	4		5	6	7

HEAP				A

			M		L

		E	      

Rebuild the heap.

    
LIST		M	E	L	A	|	S	T	Y
INDEX	1	2	3	4		5	6	7

HEAP				M

			E		L

		A	      

Pass 3 complete 

Pass 4 Exchange M and A

LIST		A	E	L	M	|	S	T	Y
INDEX	1	2	3	4		5	6	7

HEAP				A

			E		L

Rebuild the heap.

LIST		L	E	A	|	M	S	T	Y
INDEX	1	2	3		4	5	6	7

HEAP				L

			E		A

Pass 4 complete

Pass 5 Exchange L and A

LIST		A	E	|	L	M	S	T	Y
INDEX	1	2		3	4	5	6	7

HEAP				A

			E		

Rebuild the heap.

LIST		E	A	|	L	M	S	T	Y
INDEX	1	2		3	4	5	6	7

HEAP				E

			A		

Pass 5 complete

Pass 6 Exchange E and A.

LIST		A	|	E	L	M	S	T	Y
INDEX	1		2	3	4	5	6	7

Rebuild the heap. 

HEAP				A

Pass 6 complete

The list is now sorted. 


We can now describe the code for HEAPSORT in more detail. The procedure DOWNHEAP moves the element of index K to its proper position in the heap.

(******************************************************************)

procedure heapsort (var LIST: LIST_TYPE; SIZE: integer);

{PURPOSE:	This procedure implements HEAPSORT}

{INPUT:	LIST - the list to be sorted
		SIZE - the size of the list}

{OUTPUT:	LIST - the sorted list}

{DICTIONARY OF LOCAL VARIABLES:
	K - 	loop control variable
	N - 	size of the heap at each step}

var	K,  N: integer; 

begin

	for K := (M div 2) downto 1 do
		DOWNHEAP (LIST, K, SIZE);

	N := SIZE;

	repeat 
		exchange LIST [1] and LIST [N];
		N := N - 1;
		DOWNHEAP (LIST, 1, N);
	until N <= 1;
end;

(******************************************************************)

procedure downheap (var HEAP: LIST_TYPE; K, N: integer);

{PURPOSE:	This procedure moves the appropriate element of a heap to its proper position.}

{INPUT:	LIST 	- the heap
		K	- the index of the element ot be moved
		N	- the size of the heap}

{OUTPUT:	LIST - the heap with the appropriate element in place}

{DICTIONARY OF LOCAL VARIABLES
	DONE - a variable to indicate when the algorithm terminates
	J	- an index to the list}

var DONE: boolean; J: integer; 

begin

	while (K <= N div 2) and not DONE do begin

		J := 2*K;			{Find the larger child}
		if J < N then
			If HEAP [J] < HEAP [J + 1] then
				J := J + 1;
						[Switch if necessary}
		if HEAP [K] > HEAP [J] then 
			DONE := true 
		else switch HEAP [J] and HEAP [K];
		K := J;
	end;
end;
(******************************************************************)

Analysis 

Proposition Bottom-up heap construction is linear-time. 

Proposition HEAPSORT uses about 2N lg N comparisons for a list of size N.