location-aware entries in order to implement methods removereplacekeyand replacevalue of an adapt able priority queue pwe need mechanism for finding the position of an entry of namelygiven the entry of passed as an argument to one of the above methodswe need to find the position storing in the the data structure imple menting (for examplea doubly linked list or heapthis position is called the location of the entry instead of searching for the location of given entry ewe augment the entry object with an instance variable of type position storing the location this im plementation of an entry that keeps track of its position is called location-aware entry summary description of the the use of location-aware entries for the sorted list and heap implementations of an adaptable priority queue is provided below we denote the number of entries in the priority queue at the time an operation is per formedwith sorted list implementation in this implementationafter an entry is insertedwe set the location of the entry to refer to the position of the list containing the entry alsowe update the location of the entry whenever it changes position in the list operations remove(eand replacevalue( ,xtake ( timesince we can obtain the position of entry in ( time following the location reference stored with the entry insteadoperation replacekey(ekruns in (ntimebecause the modification of the key of entry may require moving the entry to different position in the list to preserve the ordering of the keys the use of location-aware entries increases the running time of the standard priority queue operations by constant factor heap implementation in this implementationafter an entry is insertedwe set the location of the entry to refer to the node of the heap containing the entry alsowe update the location of the entry whenever it changes node in the heap (for examplebecause of the swaps in down-heap or up-heap bubblingoperation replacevalue( ,xtakes ( time since we can obtain the position of entry in ( time following the location reference stored with the entry operations remove(eand replacekey( ,krun instead in (logn(details are explored in exercise - the use of location-aware entries increases the running time of operations insert and removemin by constant factor overhead the use of location-aware entries for the unsorted list implementation is explored in exercise - performance of adaptable priority queue implementations