Heaps Priority Queues Priority queue 9 Is a data structure for maintaining a set of elements each associated with a key e Maximum priority queue supports the following operations INSERT(S, x) Insert element x into the set s MAXIMUM(S Return the 'largest element EXTRACT-MAX(S)-Remove and return the 'largest element INCREASE-KEY(S, x,v)-Increase x's key to a new value, V We can implement priority queues based on a heap structure CS3381 Des Anal of Alg(2001-2002 SemA) City Univ of HK /Dept of CS Helena Wong http://www.cs.cityu.edu.hk/-helena 6. Graph Algorithms-8CS3381 Des & Anal of Alg (2001-2002 SemA) City Univ of HK / Dept of CS / Helena Wong http://www.cs.cityu.edu.hk/~helena 6. Graph Algorithms - 8 Heaps & Priority Queues Priority queue Is a data structure for maintaining a set of elements each associated with a key. Maximum priority queue supports the following operations: INSERT(S,x) - Insert element x into the set S MAXIMUM(S) - Return the ‘largest’ element EXTRACT-MAX(S) - Remove and return the ‘largest’ element INCREASE-KEY(S,x,v) - Increase x’s key to a new value, v We can implement priority queues based on a heap structure