ヒープソートの実装

はじめに

C++ を勉強したり、久々にコードを書いたりしている経緯で、
練習用に、[Cormen+Leiserson+Rivest+Stein 01] Introduction to Algorithms 2nd edition の Chap. 6 から、
ヒープソートを実装したので貼り付けました。



サブルーチンの切り分けは、
pp127〜142 に記載の擬似コードにできるだけ忠実にしました。
エレガントで新しいデバッグ技法をほとんど存じ上げない為、
「cout」がデバッグ用に頻出しております。



main 関数内に「/* */」のコメントが膨大にありますが、
これは関数それぞれのテスト用です。
こちらも、エレガントで新しいテスト技法をほとんど存じ上げない為、
こういうテストをしております。

課題

• エレガントで新しいデバッグ技法とテスト技法を習得する。
• しっかりしたコーディングスタイルを身に着ける。

ソースコード

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <math.h>

using namespace std;

#define INFTY 99999

/* prototype declarations */
int parent(int);
int left(int);
int right(int);

void hsort(int []);
void max_heapify(int [], int);
void build_max_heap(int []);
void swap(int [], int, int);

int heap_maximum(int []);
int heap_extract_max(int []);

void heap_increase_key(int [], int, int);
void max_heap_insert(int[], int);

void build_max_heap_p(int []);

int heap_size = 4;

/* a main function */
main()
{
  int v[5] = {2, 3, 5, 1, 4};
  int i;

  /* heap sort
  hsort(v);
  for (i = 0; i <= 4; i++)
  cout << v[i] << " ";

  cout << "\n";
  */

  /* build max heap and heap extract max
  build_max_heap(v);
  for (i = 0; i <= heap_size; i++)
  cout << v[i] << " ";

  cout << "\n";
  
  cout << "heap_extract_max = " << heap_extract_max(v) << "\n\n";
  for (i = 0; i <= heap_size ; i++)
  cout << v[i] << " ";

  cout << "\n";
  */

  /* build max heap and increase key and insert key
  build_max_heap(v);
  for (i = 0; i <= heap_size; i++)
  cout << v[i] << " ";

  cout << "\n";
  
  heap_increase_key(v, 4, 8); 
  cout << "heap_increase_key 3 to 8 \n\n";
  for (i = 0; i <= heap_size ; i++)
  cout << v[i] << " ";

  cout << "\n";

  max_heap_insert(v, 3);
  cout << "insert 3 \n\n";
  for (i = 0; i <= heap_size ; i++)
  cout << v[i] << " ";

  cout << "\n";
  */

  /* build max heap' */

  cout << "input \n";

  for (i = 0; i <= heap_size; i++)
  cout << v[i] << " ";

  cout << "\n";

  cout << "build_max_heap' \n";
  build_max_heap_p(v);
  for (i = 0; i <= heap_size; i++)
  cout << v[i] << " ";

  cout << "\n";

  return 0;
}

void hsort(int v[])
{
  int length_v = 4;
  int i, j;
  
  build_max_heap(v);
  cout << "build max heap has done.\n\n";

    for (i = 0; i <=4; i++)
    cout << v[i] << " ";

  cout << "\n";
  cout << "heap_maximum = " << heap_maximum(v) << "\n";

  cout << "a main routine of a heap sort starts.\n\n";
  
  for (i = length_v; i >= 2; i--) {
    cout << "length_v are down to 2. Now i = " << i << "\n";
    swap(v, 0, i);
    cout << "swap(v, 0, i): i = " << i << "\n";
 
    for (j = 0; j <= heap_size; j++){
    cout << v[j] << " ";
    }
    cout << "\n";

    heap_size--;
    max_heapify(v, 0);
  }
}

void max_heapify(int v[], int i)
{
  int l = left(i);
  int r = right(i);
  int largest;

  if ((l <= heap_size) && (v[l] > i)){
    largest = l;
    cout << "a largest is left:" << l << "\n";  
  }
  else {
    largest = i;
    cout << "a largest is i:" << i << "\n";  
  }
  if ((r <= heap_size) && (v[r] > v[largest])){
    largest = r;
    cout << "a largest is right:" << r << "\n";  
  }
  if (largest != i){
    cout << "Since a largest is not i, swap and max_heapify:" << i <<"\n";  
    swap(v, i, largest);

    for (i = 0; i <=4; i++)
    cout << v[i] << " ";

  cout << "\n";

  cout << "Now, max_heapify recursively calls max heapify.\n";

    max_heapify(v, largest);
  }
}

void build_max_heap(int v[])
{
  int length_v = 4;
  int i;

  for (i = int(floor(length_v / 2) - 1); i >= 0; i--){
    cout << "build max heap: i = " << i << " max heapify starts.\n";
    max_heapify(v, i);
    cout << "\n\n";
  }
}

void swap(int v[], int i, int j)
{
  int temp; 

  temp = v[i];
  v[i] = v[j];
  v[j] = temp;
  cout << i << " and " << j << " are swapped. \n";
}

int parent(int i)
{
  cout << "a parent is " << int(floor((i - 1) / 2)) << "\n"; 
  return int(floor((i - 1) / 2));
}

int left(int i)
{
  cout << "a left is " << 2 * i + 1 << "\n"; 
  return 2 * i + 1;
}

int right(int i)
{
  cout << "a right is " << 2 * i + 2 << "\n"; 
  return 2 * i + 2;
}

int heap_maximum(int v[])
{
  return v[0];
}

int heap_extract_max(int v[])
{
  int max;

  if (heap_size < 0) {
    cout << "heap underflow \n";
  }

  max = v[0];
  v[0] = v[heap_size];
  heap_size--;
  max_heapify(v, 0);
  return max;
}

void heap_increase_key(int v[], int i, int key)
{
  if (key < v[i]) {
    cout << "new key is smaller than current key\n";
  }
  v[i] = key;
  while ((i > 0) && v[parent(i)] < v[i]) {
    swap(v, i, parent(i));
    i = parent(i);
  }
}

void max_heap_insert(int v[], int key)
{
  heap_size++;
  v[heap_size] = -INFTY;
  heap_increase_key(v, heap_size, key);
}

void build_max_heap_p(int v[])
{
  int i;

  heap_size = 0;
  for (i = 1; i <= 4; i++){
    max_heap_insert(v, v[i]);
  }
}