cでHeap実装 （データ構造とアルゴリズム）

入門データ構造とアルゴリズムから

#include "stdafx.h"
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#define MAX_VAL 99999
using namespace std;

struct Heap {
    int *array;
    int count;
    int capacity;
    int heap_type;
    };
 struct Heap *CreateHeap(int capacity, int heap_type) {
    struct Heap *h = (struct Heap *)malloc(sizeof(struct Heap));
    if (h == NULL) {
        cout << "Memory error" << endl;
        return NULL;
    }
    h->heap_type = heap_type;
    h->count = 0;
    h->capacity = capacity;
    h->array = (int *)malloc(sizeof(int)*h->capacity);
    if (h->array == NULL) {
        cout << "Memory error" << endl;
        return NULL;
    }
    for (int i = 0; i < h->capacity; i++) {
        h->array[i] = NULL;
    }

    cout << "Create Heap !" << endl;
    cout << "heap_type " << h->heap_type << endl;
    cout << "caoacity  " << h->capacity << endl;

    return h;
}
 int Parent(struct Heap *h, int i) {
     if (i <= 0 || i >= h->count) {
         cout << "Eorror parent " << endl;
         return -1;
     }
     cout << "parent No. "<< (i - 1) / 2<<endl;
     return (i - 1) / 2;
 }
 int LeftChildlen(struct Heap *h, int i) {
     int left = 2 * i + 1;
     if (left >= h->count)return -1;
     cout << "child No. " << left << endl;
     return left;
 }
 int RightChildlen(struct Heap *h, int i) {
     int right = 2 * i + 2;
     if (right >= h->count)return -1;
     cout << "child No. " << right << endl;
     return right;
 }
 int GetMaximum(struct Heap *h) {
     if (h->count == 0)return -1;
     cout << "Maximum No. " << h->array[0] << endl;
     return h->array[0];
 }
 void ResizeHeap(struct Heap *h) {
     int *array_old = h->array;
     h->array = (int *)malloc(sizeof(int) * h->capacity * 2);
     if (h->array == NULL) {
         cout << "Memory Error ";
         return;
     }
     for (int i = 0; i < h->capacity; i++) {
         h->array[i] = array_old[i];
     }
     h->capacity *= 2;
     free(array_old);

 }
 void insert(struct Heap *h, int data) {
     int i;
     if (h->count == h->capacity) ResizeHeap(h);
     h->count++;
     i = h->count - 1;
     while (i >= 0 && data > h->array[(i - 1) / 2]) {
         h->array[i] = h->array[(i - 1) / 2];
         i = (i - 1) / 2;
     }
     h->array[i] = data;

 }

 void PrecolateDown(struct Heap *h, int i) {
     int l, r, max, temp;
     l = LeftChildlen(h, i);
     r = RightChildlen(h, i);
     if (l != -1 && h->array[l] > h->array[i]) max = 1;
     max = i;
     if (r != -1 && h->array[r] > h->array[max]) max = r;
     if (max != i) {
         temp = h->array[i];
         h->array[i] = h->array[max];
         h->array[i] = temp;
     }
     PrecolateDown(h, max);
 }
 void show(struct Heap *h) {
     for (int i = 0; i<h->capacity; i++) {
         cout<<"heap["<< i << "] = " << h->array[i] << endl;
     }
 }

int _tmain(int argc, _TCHAR* argv[])
{
    struct Heap *heap = CreateHeap(10, 2);
    heap->array[0] = MAX_VAL;
    insert(heap, 900);
    insert(heap, 20);
    insert(heap, 120);
    insert(heap, 220);
    insert(heap, 320);
    insert(heap, 520);
    insert(heap, 880);
    insert(heap, 820);
    insert(heap, 180);
    insert(heap, 800);
    insert(heap, 390);
    insert(heap, 10);
    insert(heap, 40);
    insert(heap, 710);

    Parent(heap, 4);
    LeftChildlen(heap, 4);
    GetMaximum(heap);


    Parent(heap, 4);
    LeftChildlen(heap, 4);
    GetMaximum(heap);
    show(heap);
    //PrecolateDown(heap, 2);
    return 0;
}

実行結果

Create Heap !
heap_type 2
caoacity 10
parent No. 1
child No. 9
Maximum No. 900
parent No. 1
child No. 9
Maximum No. 900
heap[0] = 900
heap[1] = 820
heap[2] = 880
heap[3] = 320
heap[4] = 800
heap[5] = 120
heap[6] = 710
heap[7] = 20
heap[8] = 180
heap[9] = 220
heap[10] = 390
heap[11] = 10
heap[12] = 40
heap[13] = 520
heap[14] = -842150451
heap[15] = -842150451
heap[16] = -842150451
heap[17] = -842150451
heap[18] = -842150451
heap[19] = -842150451