Solve in Java Your task for this problem is to create a priority queue and apply it to solve the Almost Shortest Path problem. Implementing a Binary Heap to Use as a Priority Queue

Attributes:

An internal array to store the elements contained in the heap.

An integer attribute to store the size of the heap. The size is equal to the number of elements in the heap, not the size of the array.

A dictionary or map structure to serve as a lookup table so the index of any given element can be found in O(1) time (on average). In the text this attribute is named, Position. For each entry in the dictionary, the key would be the item, and the value would be the index where the item is stored. If you use string or integer data for your input, you can use the item itself as the key. The dictionary will be used to implement the ChangeKey() method.

Supporting Components

A HeapNode component or class that represents an individual node of the heap. This component is essential in order to be able to store both an items data value and its priority value together in the heap. Do not assume an items data value and its priority value are one and the same. --------------------------------------------------------------------------------------------------------------------------------------------

Heapify_Up(index) moves an element located at the specified index upwards in the heap to correctly reposition an element whose value is less than the value of its parent. This condition may result from removing an element or from changing an elements value. This method is described on pages 60-61 of the text, and pseudocode is provided on page 61.

Heapify_Down(index) moves an element located at the specified index downwards in the heap to correctly reposition an element whose value is greater than the value of either of its children. This condition may result from removing an element or from changing an elements value. This method is described on pages 62-63 of the text, and pseudocode is provided on page 63.

StartHeap(N) initializes an empty heap that is set up to store at most N elements. This operation takes O(N) time, as it involves initializing the array that will hold the heap.

Insert(item, value) inserts the item, item, with an ordering value, value, into the heap at the end of the array, then uses Heapify_Up to position the item so as to maintain the heap order. If the heap currently has n elements, this takes O(log n) time.

FindMin() identifies the minimum element in the heap, which is located at index 1, but does not remove it. This takes O(1) time.

Delete(index) deletes the element in the specified heap position by moving the item in the last array position to index, then using Heapify_Down to reposition that item. This is implemented in O(log n) time for heaps that have n elements.

ExtractMin() identifies and deletes the element with the minimum key value, located at index 1, from the heap. This is a combination of the preceding two operations, and so it takes O(log n) time.

Delete(item) deletes the element item form the heap. This can be implemented as a call to Delete(Position[item]), which operates in O(logn) time for heaps that have n elements provided Position allows the index of v to be returned in O(1) time.

ChangeKey(item, newValue), which changes the priority value of element v to newValue. To implement this operation in O(logn) time, we first need to be able to identify the position of element v in the array, which we do by using the position dictionary(look-up table). Once we have identified the position of element v, we change the key and then apply Heapify-up or Heapify-down as appropriate. You will need to use ChangeKey() method in Part II while implementing Dijkstra Algorithm. -------------------------------------------------------------------------------------------------------------------------------------------- AVOID THESE MISTAKES

In Heapify_Up(index) and Heapify_Down(index), forget to update position accordingly. You will need to update position lookup-table while you move notes up and down.

After ChangeKey, forget to heapify, since after modification, the heap property does not hold anymore.

Not implementing position lookup table. You will need to do this.