データ構造アルゴリズム学習-優先キュー-二叉スタック
2450 ワード
優先キュー定義
優先キューは、少なくとも2つの操作があるデータ構造です.挿入(Insert)、最小者(DeleteMin)の削除です.
フォークスタック定義
二叉山抽象概念は完全に満たされた二叉木(底層には例外があるかもしれない)であり、親子関係が規則的であるため(任意の位置i上の要素、父はabs(i/2)、左息子は2 i上、息子は2 i+1上、左シフト右シフト操作で乗算を実現)、ポインタ(チェーンテーブル)を必要とせずに配列で実現することができる.
アルゴリズム実装
優先キューは、少なくとも2つの操作があるデータ構造です.挿入(Insert)、最小者(DeleteMin)の削除です.
フォークスタック定義
二叉山抽象概念は完全に満たされた二叉木(底層には例外があるかもしれない)であり、親子関係が規則的であるため(任意の位置i上の要素、父はabs(i/2)、左息子は2 i上、息子は2 i+1上、左シフト右シフト操作で乗算を実現)、ポインタ(チェーンテーブル)を必要とせずに配列で実現することができる.
アルゴリズム実装
/* Elr Heap Int Source */
#include
#include
#include "elr_heap_int.h"
#define parent(x) (x >> 1)
#define left(x) (x << 1)
#define right(x) (x << 1 + 1)
pHeap elrInitHeap(int capaticy) {
pHeap s;
s = malloc(sizeof(sHeap));
if (s == NULL) {
printf("out of space!");
}
s->data = malloc(sizeof(long long int) * (capaticy + 1));
if (s->data == NULL) {
printf("out of space!");
}
s->capacity = capaticy;
s->size = 0;
s->data[0] = -1;
return s;
}
void elrFreeHeap(pHeap info) {
if (info != NULL) {
free(info->data);
free(info);
}
}
int elrIsHeapEmpty(pHeap info) {
return info->size == 0;
}
int elrIsHeapFull(pHeap info) {
return info->size == info->capacity;
}
void elrPushHeap(pHeap info, long long int value) {
int i;
if (elrIsHeapFull(info)) {
printf("full heap");
} else {
for (i = ++info->size; info->data[parent(i)] > value; i = parent(i)) {
info->data[i] = info->data[parent(i)];
}
info->data[i] = value;
}
}
long long int elrFindHeapMin(pHeap info) {
if (elrIsHeapEmpty(info)) {
printf("empty heap");
return info->data[0];
} else {
return info->data[1];
}
}
long long int elrDeleteHeapMin(pHeap info) {
int i, child;
long long int min, last;
if (elrIsHeapEmpty(info)) {
printf("empty heap");
return info->data[0];
} else {
min = info->data[1];
last = info->data[info->size--];
for (i = 1; left(i) <= info->size; i = child) {
child = left(i);
if ((child != info->size) && (info->data[child] >= info->data[child + 1])) {
child++;
}
if (last > info->data[child]) {
info->data[i] = info->data[child];
} else {
break;
}
}
info->data[i] = last;
return min;
}
}