heap.cpp

来自「数据结构与程序设计教材源码 数据结构与程序设计教材源码」· C++ 代码 · 共 74 行

 
template <class Record>
void Sortable_list<Record>::insert_heap(const Record &current, int low, int high)
/* 
 
Pre:  The entries of the Sortable_list between indices low + 1 and high,
     inclusive, form a heap. The entry in position low will be discarded.
Post: The entry current has been inserted into the Sortable_list
      and the entries rearranged
      so that the entries between indices low and high, inclusive,
      form a heap.
Uses: The class Record, and the contiguous List implementation of
      ?list_ch?.
 
*/
 
{
   int large;              //  position of child of entry[low] with the larger key

   large = 2 * low + 1;    //  large is now the left child of low.
   while (large <= high) {
      if (large < high && entry[large] < entry[large + 1])
         large++;          //  large is now the child of low with the largest key.
      if (current >= entry[large])
         break;            //  current belongs in position low.

      else {               //  Promote entry[large] and move down the tree.
         entry[low] = entry[large];
         low = large;
         large = 2 * low + 1;
      }
   }
   entry[low] = current;
}
 
template <class Record>
void Sortable_list<Record>::build_heap()
/* 
 
Post: The entries of the Sortable_list have been rearranged so that it becomes a heap.
Uses: The contiguous List implementation of ?list_ch?, and insert_heap.
 
*/

{
   int low;   //  All entries beyond the position low form a heap.
   for (low = count / 2 - 1; low >= 0; low--) {
      Record current = entry[low];
      insert_heap(current, low, count - 1);
   }
}
 
template <class Record>
void Sortable_list<Record>::heap_sort()
/* 
 
Post: The entries of the Sortable_list have been rearranged so
that their keys are sorted into nondecreasing order.
Uses: The contiguous List implementation of ?list_ch?,
      build_heap, and insert_heap.
 
*/

{
   Record current;    //  temporary storage for moving entries
   int last_unsorted; //  Entries beyond last_unsorted have been sorted.
   build_heap();      //  First phase:  Turn the list into a heap.
   for (last_unsorted = count - 1; last_unsorted > 0; last_unsorted--) {
      current = entry[last_unsorted];   //  Extract the last entry from the list.
      entry[last_unsorted] = entry[0];     //  Move top of heap to the end
      insert_heap(current, 0, last_unsorted - 1);  //  Restore the heap
   }
}