Chapter 9
Priority Queues
9.1 Introduction
? A priority queue is a collection of zero or
more elements,Each element has a priority
or value.
? Operations:
1)find an element
2)insert a new element
3)delete an element
9.1 Introduction
? In a min priority queue the find operation
finds the element with minimum priority,
while the delete operation delete this
element.
? In a max priority queue,the find operation
finds the element with maximum priority,
while the delete operation delete this
element.
9.1 Introduction
? ADT of a max priority queue
AbstractDataType MaxPriorityQueue{
instances
finite collection of elements,each has a priority
operations
create(),create an empty priority queue
Size(),return number of element in the queue
Max(),return element with maximum priority
Insert(x),insert x into queue
DeleteMax(x):delete the element with largest
priority from the queue;return it in x;
}
9.2 Linear List Representation
? Use an unordered linear list
? Insertions are performed at the right end of
the list,θ(1)
? A deletion requires a search for the element
with largest priority,θ(n)
9.3 Heaps
1.definition,A max heap(min Heap)
? is A complete binary tree
? The value in each node is greater(less) than
or equal to those in its children(if any).
9.3 Heaps
? For example:an max heap
k={87,78,53,45,65,09,31,17,23}
87
78
45 65
53
09
17
31
23
9.3 Heaps
? Example of min heap
k={09,17,65,23,45,78,87,53,31}
09
17
23 45
65
78
53
87
31
9.3 Heaps
2.class MaxHeap
Data member of heap,
T * heap; int MaxSize,currentSize
template<class T>class Maxheap
{ public:
MaxHeap(int MaxHeapSize=10);
~MaxHeap(){delete[]heap;}
int size()const{return currentSize;}
9.3 Heaps
T Max(){if (CurrentSize==0)throw OutOfBounds();
return heap[1];}
MaxHeap<T>&insert(const T&x);
MaxHeap<T>& DeleteMax(T& x);
void initialize(T a[],int size,int ArraySize);
private,
int CurrentSize,MaxSize;
T * heap;
}
9.3 Heaps
3.member function of MaxHeap
1)constructor for MaxHeap
template<class T>
MaxHeap<T>::MaxHeap(int MaxHeapSize)
{ MaxSize=MaxHeapSize;
Heap=new T[MaxSize+1];
CurrentSize=0;
}
9.3 Heaps
2)Insertion into a max heap
Example:
20
15 2
14 10 21014
20
21
15Insert 21
9.3 Heaps
? Program 9.3 insertion
template<class T>MaxHeap<T>& MaxHeap<T>:,
Insert(const T& x)
{ if(CurrentSize==MaxSize)throw NoMem();
int i=++CurrentSize;
while(i!=1&&x>heap[i/2])
{heap[i]=heap[i/2]; i/=2;}
heap[i]=x; return *this;
}
time complexity is O(log2n)
9.3 Heaps
3)deletion
21
10
2015
214 1014
2015
2
1014
215
20
9.3 Heaps
? Program 9.4 deletion from a max heap
template<class T>MaxHeap<T>&
MaxHeap<T>::DeleteMax(T& x)
{ if (CurrentSize==0)throw OutofBounds();
x=heap[1];
T y=heap[CurrentSize--];
int i=1;ci=2;
while(ci<=currentSize)
{if(ci<currentSize&&heap[ci]<heap[ci+1]) ci++;
9.3 Heaps
if(y>=heap[ci]) break;
heap[i]=heap[ci];
i=ci;ci*=2;
}
heap[i]=y;
return *this;
}
Time complexity is O(log2n)
9.3 Heaps
4)Initialize a nonempty max heap
Example,[20,12,35,15,10,80,30,17,2,1]
20
12 35
15 10 80 30
17 2 1
[1]
[2] [3]
[4] [5] [6] [7]i
[8] [9]
[10]
i=[n/2],[n/2]-1,…,1
?Turn into max heap from
these subtree roots
9.3 Heaps
Program 9.5 initialize
Template<class T> void MaxHeap<T>::Initialize
(T a[],int size,int ArraySize)
{ delete[] heap;
heap=a; CurrentSize=Size; MaxSize=ArraySize;
for(int i=currentSize/2; i>=1;i--)
{T y=heap[i];
int c=2*i;
9.3 Heaps
while(c<=CurrentSize)
{ if(c<CurrentSize&&heap[c]<heap[c+1]) c++;
if(y>=heap[c])break;
heap[c/2]=heap[c];
c*=2;
}
heap[c/2]=y;
}
}
9.3 Heaps
Public member Deactivate:
? void Deactivate(){heap=0;}
? The function is used to avoid the deletion of
the array a when the heap destructor is
invoked.
9.4.Application
1.heap sort
? Method:
1)initialize a max heap with the n elements to
be sorted O(n)
2)each time we delete one element,then
adjust the heap O(log2n)
9.4.Application
? Example,{21,25,49,25*,16,08}
? Time complexity is
O(n)+O(n*log2n)=O(n*log2n)
9.4.Application
? Heap sort
template<class T>
void HeapSort(T a[],int n)
{MaxHeap<T> H(1);
H.Initialize(a,n,n);
T x;
for(int i=n-1;i>=1;i--){
H.DeleteMax(x);
a[i+1]=x;
} H.Deactivate();
}
9.4.Application
2.Huffman tree and Huffman codes
1)concepts relating to extended binary tree
? Extended binary tree:
for elements in the original binary tree with
degree 1,add a null leaf
for elements in the original binary tree with
degree 0,add two null leaves
9.4.Application
? example
--internal node
--external node
9.4.Application
? external path length E,the sum of all path
length from the root to every external nodes
E=3+3+2+3+4+4+3+3=25
? internal path length I,the sum of all path
length from the root to every internal nodes
I=2+1+0+3+2+2+1=11
9.4.Application
? Weighted path length of a node,
? Weighted external path length:sum of all
leaf nodes’ weighted path length
? Weighted internal path length,sum of all
non-leave nodes’ weighted path length
9.4.Application
2)Question:
Given w1,w2,……w m(m>=2,wi is a real
number) as the weight of m external nodes,
we can construct a extended binary tree and
make its ?wili minimal.
i=1
m
9.4.Application
? Example,weight of external nodes are
2,3,4,11,then we can construct
11 2
4
32 4 11
3 432 11
11*1+4*2+(2+3)*3=34 53 40
9.4.Application
? Huffman algorithm
Algorithm,select two element with minimum
weights w1 and w2 to construct
w
w1 w2
W=W1+W2
then sorted the m-1 weights(w,w3,w4,……w m)
into a increased sequence,and apply the
algorithm on it again.
9.4.Application
? Example,2,3,5,7,11,13,17,19,23,29,
31,37,41
Class declaration of extended binary tree
template<class Type> class ExtBinTree;
template<class Type> class Element
{friend class ExtBinTree<Type>;
private:
Element<Type>* leftchild,*rightchild;
Type data;
};
template<class Type> class ExtBinTree
{ public:
ExtBinTree(ExtBinTree<Type>& bt1,ExtBinTree<Type>&bt2)
9.4.Application
{
root->leftchild=bt1.root;
root->rightchild=bt2.root;
root->data.key=bt1.root->data.key+bt2.root-
>data.key;
}
protected:
const int DefaultSize=20;
Element<Type>* root;
MinHeap<ExtBinTree<Type>> hp;
};
9.4.Application
Algorithm of constructing a huffman tree
template<class Type>
void HuffmanTree(Type *fr,int n,ExtBinTree<Type>& newtree)
{
ExtBinTree<Type>& first,&second;
ExtBinTree<Type> Node[Defaultsize];
if(n>Defaultsize)
{ cerr<<“Size n”<<n<<,exceeds the boundary of Array\n”;
return ; }
for(int I=0; I<n; I++)
{ Node[I].root->data.key=fr[I];
9.4.Application
Node[I].root->leftchild=Node[I].root->rightchild=NULL;
}
hp.MinHeap(Node,n);
for(int I=0; I<n-1; I++)
{
hp.DeleteMin(first);
hp.DeleteMin(second);
newtree=new ExtBinTree<Type>(first,second);
hp.Insert(newtree);
}
return hp.RemoveMin(newtree);
}
9.4.Application
3)huffman code
Priority Queues
9.1 Introduction
? A priority queue is a collection of zero or
more elements,Each element has a priority
or value.
? Operations:
1)find an element
2)insert a new element
3)delete an element
9.1 Introduction
? In a min priority queue the find operation
finds the element with minimum priority,
while the delete operation delete this
element.
? In a max priority queue,the find operation
finds the element with maximum priority,
while the delete operation delete this
element.
9.1 Introduction
? ADT of a max priority queue
AbstractDataType MaxPriorityQueue{
instances
finite collection of elements,each has a priority
operations
create(),create an empty priority queue
Size(),return number of element in the queue
Max(),return element with maximum priority
Insert(x),insert x into queue
DeleteMax(x):delete the element with largest
priority from the queue;return it in x;
}
9.2 Linear List Representation
? Use an unordered linear list
? Insertions are performed at the right end of
the list,θ(1)
? A deletion requires a search for the element
with largest priority,θ(n)
9.3 Heaps
1.definition,A max heap(min Heap)
? is A complete binary tree
? The value in each node is greater(less) than
or equal to those in its children(if any).
9.3 Heaps
? For example:an max heap
k={87,78,53,45,65,09,31,17,23}
87
78
45 65
53
09
17
31
23
9.3 Heaps
? Example of min heap
k={09,17,65,23,45,78,87,53,31}
09
17
23 45
65
78
53
87
31
9.3 Heaps
2.class MaxHeap
Data member of heap,
T * heap; int MaxSize,currentSize
template<class T>class Maxheap
{ public:
MaxHeap(int MaxHeapSize=10);
~MaxHeap(){delete[]heap;}
int size()const{return currentSize;}
9.3 Heaps
T Max(){if (CurrentSize==0)throw OutOfBounds();
return heap[1];}
MaxHeap<T>&insert(const T&x);
MaxHeap<T>& DeleteMax(T& x);
void initialize(T a[],int size,int ArraySize);
private,
int CurrentSize,MaxSize;
T * heap;
}
9.3 Heaps
3.member function of MaxHeap
1)constructor for MaxHeap
template<class T>
MaxHeap<T>::MaxHeap(int MaxHeapSize)
{ MaxSize=MaxHeapSize;
Heap=new T[MaxSize+1];
CurrentSize=0;
}
9.3 Heaps
2)Insertion into a max heap
Example:
20
15 2
14 10 21014
20
21
15Insert 21
9.3 Heaps
? Program 9.3 insertion
template<class T>MaxHeap<T>& MaxHeap<T>:,
Insert(const T& x)
{ if(CurrentSize==MaxSize)throw NoMem();
int i=++CurrentSize;
while(i!=1&&x>heap[i/2])
{heap[i]=heap[i/2]; i/=2;}
heap[i]=x; return *this;
}
time complexity is O(log2n)
9.3 Heaps
3)deletion
21
10
2015
214 1014
2015
2
1014
215
20
9.3 Heaps
? Program 9.4 deletion from a max heap
template<class T>MaxHeap<T>&
MaxHeap<T>::DeleteMax(T& x)
{ if (CurrentSize==0)throw OutofBounds();
x=heap[1];
T y=heap[CurrentSize--];
int i=1;ci=2;
while(ci<=currentSize)
{if(ci<currentSize&&heap[ci]<heap[ci+1]) ci++;
9.3 Heaps
if(y>=heap[ci]) break;
heap[i]=heap[ci];
i=ci;ci*=2;
}
heap[i]=y;
return *this;
}
Time complexity is O(log2n)
9.3 Heaps
4)Initialize a nonempty max heap
Example,[20,12,35,15,10,80,30,17,2,1]
20
12 35
15 10 80 30
17 2 1
[1]
[2] [3]
[4] [5] [6] [7]i
[8] [9]
[10]
i=[n/2],[n/2]-1,…,1
?Turn into max heap from
these subtree roots
9.3 Heaps
Program 9.5 initialize
Template<class T> void MaxHeap<T>::Initialize
(T a[],int size,int ArraySize)
{ delete[] heap;
heap=a; CurrentSize=Size; MaxSize=ArraySize;
for(int i=currentSize/2; i>=1;i--)
{T y=heap[i];
int c=2*i;
9.3 Heaps
while(c<=CurrentSize)
{ if(c<CurrentSize&&heap[c]<heap[c+1]) c++;
if(y>=heap[c])break;
heap[c/2]=heap[c];
c*=2;
}
heap[c/2]=y;
}
}
9.3 Heaps
Public member Deactivate:
? void Deactivate(){heap=0;}
? The function is used to avoid the deletion of
the array a when the heap destructor is
invoked.
9.4.Application
1.heap sort
? Method:
1)initialize a max heap with the n elements to
be sorted O(n)
2)each time we delete one element,then
adjust the heap O(log2n)
9.4.Application
? Example,{21,25,49,25*,16,08}
? Time complexity is
O(n)+O(n*log2n)=O(n*log2n)
9.4.Application
? Heap sort
template<class T>
void HeapSort(T a[],int n)
{MaxHeap<T> H(1);
H.Initialize(a,n,n);
T x;
for(int i=n-1;i>=1;i--){
H.DeleteMax(x);
a[i+1]=x;
} H.Deactivate();
}
9.4.Application
2.Huffman tree and Huffman codes
1)concepts relating to extended binary tree
? Extended binary tree:
for elements in the original binary tree with
degree 1,add a null leaf
for elements in the original binary tree with
degree 0,add two null leaves
9.4.Application
? example
--internal node
--external node
9.4.Application
? external path length E,the sum of all path
length from the root to every external nodes
E=3+3+2+3+4+4+3+3=25
? internal path length I,the sum of all path
length from the root to every internal nodes
I=2+1+0+3+2+2+1=11
9.4.Application
? Weighted path length of a node,
? Weighted external path length:sum of all
leaf nodes’ weighted path length
? Weighted internal path length,sum of all
non-leave nodes’ weighted path length
9.4.Application
2)Question:
Given w1,w2,……w m(m>=2,wi is a real
number) as the weight of m external nodes,
we can construct a extended binary tree and
make its ?wili minimal.
i=1
m
9.4.Application
? Example,weight of external nodes are
2,3,4,11,then we can construct
11 2
4
32 4 11
3 432 11
11*1+4*2+(2+3)*3=34 53 40
9.4.Application
? Huffman algorithm
Algorithm,select two element with minimum
weights w1 and w2 to construct
w
w1 w2
W=W1+W2
then sorted the m-1 weights(w,w3,w4,……w m)
into a increased sequence,and apply the
algorithm on it again.
9.4.Application
? Example,2,3,5,7,11,13,17,19,23,29,
31,37,41
Class declaration of extended binary tree
template<class Type> class ExtBinTree;
template<class Type> class Element
{friend class ExtBinTree<Type>;
private:
Element<Type>* leftchild,*rightchild;
Type data;
};
template<class Type> class ExtBinTree
{ public:
ExtBinTree(ExtBinTree<Type>& bt1,ExtBinTree<Type>&bt2)
9.4.Application
{
root->leftchild=bt1.root;
root->rightchild=bt2.root;
root->data.key=bt1.root->data.key+bt2.root-
>data.key;
}
protected:
const int DefaultSize=20;
Element<Type>* root;
MinHeap<ExtBinTree<Type>> hp;
};
9.4.Application
Algorithm of constructing a huffman tree
template<class Type>
void HuffmanTree(Type *fr,int n,ExtBinTree<Type>& newtree)
{
ExtBinTree<Type>& first,&second;
ExtBinTree<Type> Node[Defaultsize];
if(n>Defaultsize)
{ cerr<<“Size n”<<n<<,exceeds the boundary of Array\n”;
return ; }
for(int I=0; I<n; I++)
{ Node[I].root->data.key=fr[I];
9.4.Application
Node[I].root->leftchild=Node[I].root->rightchild=NULL;
}
hp.MinHeap(Node,n);
for(int I=0; I<n-1; I++)
{
hp.DeleteMin(first);
hp.DeleteMin(second);
newtree=new ExtBinTree<Type>(first,second);
hp.Insert(newtree);
}
return hp.RemoveMin(newtree);
}
9.4.Application
3)huffman code
