< Free Open Study > |
template<class ItemType> void HeapType<ItemType>::ReheapDown(int root, int bottom) // Post: Heap property is restored. { int maxChild; int rightChild; int leftChild; bool heapOK = false; while (root*2+1 <= bottom) && !heapOK) { leftChild = root*2+1; rightChild = root*2+2; if (leftChild == bottom) maxChild = leftChild; else { if (elements[leftChild] <= elements[rightChild]) maxChild = rightChild; else maxChild = leftChild; } if (elements[root] < elements[maxChild]) Swap(elements[root], elements[maxChild]); else heapOK = true; } }
template<class ItemType> void HeapType<ItemType>::ReheapUp(int root, int bottom) // Post: Heap property is restored. { int parent; bool heapOK = false; while (bottom > root && !heapOK) { parent = (bottom-1) / 2; if (elements[parent] < elements[bottom]) { Swap(elements[parent], elements[bottom]); bottom = parent; } else heapOK = true; } }
The nonrecursive versions, like the recursive versions, are O(log_{2}N).
The highest-priority element is the one with the largest time stamp. (This assumes that the time stamp never reaches INT_MAX.)
The Push operation has O(1) complexity, because it doesn't matter where the item is stored in the structure. The Pop operation has O(N) complexity, because the item with the largest time stamp must be searched for. Therefore, Push is the same in both implementations, but Pop is not. If the priority queue is implemented using a heap with the largest value having the highest priority, Pop and Push have O(log2N) complexity.
The highest-priority element is the one with the smallest time stamp.
Enqueue, like those operations in Chapter 5, has O(1) complexity. Dequeue has O(N), as compared with the O(1) operations developed in Chapter 5. If the priority queue is implemented using a heap with the smallest value having the highest priority, Enqueue has O(1) and Dequeue has O(log_{2}N) complexity.
The string length attribute is used to determine their priority (longer length is higher priority).
Deleting a vertex is more complicated than deleting an edge for two reasons. First, in addition to removing the vertex from the set of vertices, we must remove the edges to all its adjacent vertices in the set of edges. Second, we must decide how to handle the now unused vertex number. The best solution is to keep a list of returned vertex numbers and assign new numbers from there first.
Implicit set representations represent those items that are present in an instance of a set explicitly; those items that are not represented are not in the set. Explicit set representations associate a place (bit or Boolean flag) with each item in the base type in the instance of each set. The place for an item is true if the item is in the set and false if the item is not in the set.
< Free Open Study > |
Converted from CHM to HTML with chm2web Pro 2.85 (unicode) |