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

# 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