平成30年度春期基本情報技術者試験 午後 問8

h30h_fe_pm8.c

#include <stdio.h>

int lchild(int i);
int rchild(int i);
int parent(int i);
void swap(int heap[], int i, int j);
void makeHeap(int data[], int heap[], int hnum);
void heapSort(int data[], int heap[], int hnum);
void downHeap(int heap[], int hlast);
void print_array(int arr[], int num); /* 配列表示用 */

int lchild(int i)
{
  return 2*i+1;
}

int rchild(int i)
{
  return 2*i+2;
}
  
int parent(int i)
{
  return (i-1)/2;
}

void swap(int heap[], int i, int j)
{
  int tmp;
  tmp = heap[i];
  heap[i] = heap[j];
  heap[j] = tmp;
}

void makeHeap(int data[], int heap[], int hnum)
{
  int i, k;
  for (i = 0; i < hnum; i++) {
    heap[i] = data[i];
    k = i;
    while (k > 0) {
      if (heap[k] > heap[parent(k)]) { /* (a) */
        swap(heap, k, parent(k));      /* (b) */
        k = parent(k);
      }
      else {
        break;
      }
    }
  }
}

void heapSort(int data[], int heap[], int hnum)
{
  int last;
  makeHeap(data, heap, hnum);
  for (last = hnum-1; last > 0; last--) {
    swap(heap, 0, last);
    downHeap(heap, last-1);
  }
}

void downHeap(int heap[], int hlast)
{
  int n, tmp;
  n = 0;
  while (lchild(n) <= hlast) {
    tmp = lchild(n);
    if (rchild(n) <= hlast) {
      if (heap[tmp] <= heap[rchild(n)]) {
        tmp = rchild(n);
      }
    }
    if (heap[tmp] > heap[n]) {
      swap(heap, n, tmp);
    }
    else {
      return;                   /* downHeap から抜ける */
    }
    n = tmp;
  }
}

void print_array(int arr[], int num)
{
  for (int i = 0; i < num; i++) {
    printf("%3d", arr[i]);
  }
  printf("\n");

}

int main(void)
{
  int data[] = {15, 5, 30, 60, 45, 20, 10};
  int hnum = 7;
  int heap[hnum];
  printf("Before: "); print_array(data, hnum);
  heapSort(data, heap, hnum);
  printf("After : "); print_array(heap, hnum);
  return 0;
}

Before: 15 5 30 60 45 20 10
After : 5 10 15 20 30 45 60

http://maehrm.hatenablog.com/entry/2018/04/22/111630