Previous Section
 < Free Open Study > 
Next Section


Chapter 9

    1. 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;
        }
      }
      
    2. 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;
        }
      }
      
    3. The nonrecursive versions, like the recursive versions, are O(log2N).

    1. Click To expand
    2. x = 56, y = 42, z = 40

    1. The highest-priority element is the one with the largest time stamp. (This assumes that the time stamp never reaches INT_MAX.)

    2. 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.

    1. The highest-priority element is the one with the smallest time stamp.

    2. 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(log2N) complexity.

    1. The string length attribute is used to determine their priority (longer length is higher priority).

      Click To expand
  1. Click To expand
  2. Click To expand
    Click To expand
    1. Yes

    2. Yes

    3. No

    4. No

    5. Yes

    6. No

    1. No

    2. Yes

    3. Texas

    1. Click To expand
    2. Click To expand
  1. 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.

    1. Base Cases: (1) If endVertex has been previously found, stop. (2) If startVertex equals endVertex, found is true; stop. (3) If no more untried vertices are adjacent to startVertex, found is false; stop.

      General Case: If endVertex is not yet found, DepthFirstSearch all the untried adjacent vertices.

  2. 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.



Previous Section
 < Free Open Study > 
Next Section
Converted from CHM to HTML with chm2web Pro 2.85 (unicode)