we now discuss how to implement priority queue using heap our heap-based representation for priority queue consists of the following (see figure )heapa complete binary tree whose internal nodes store entries so that the heap-order property is satisfied we assume is implemented using an array listas described in section for each internal node of twe denote the key of the entry stored at as (vcompa comparator that defines the total order relation among the keys with this data structuremethods size and isempty take ( timeas usual in additionmethod min can also be easily performed in ( time by accessing the entry stored at the root of the heap (which is at index in the array listinsertion let us consider how to perform insert on priority queue implemented with heap to store new entry ( ,xinto we add new node to with operation add so that this new node becomes the last node of and stores entry ( ,xafter this actionthe tree is completebut it may violate the heap-order property henceunless node is the root of (that isthe priority queue was empty before the insertion)we compare key (zwith the key (ustored at the parent of if ( > ( )the heap-order property is satisfied and the algorithm terminates if instead (zk( )then we need to restore the heap-order propertywhich can be locally achieved by swapping the entries stored at and (see figure and this swap causes the new entry ( ,eto move up one level againthe heap-order property may be violatedand we continue swappinggoing up in until no violation of the heap-order property occurs (see figure and figure illustration of the heap-based implementation of priority queue