データ構造アルゴリズム学習-優先キュー-二叉スタック

2450 ワード

二叉の山優先列アルゴリズム-データ構造 c

優先キュー定義
優先キューは、少なくとも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;
    }
}

ubuntu16.04で動作しているapacheサーバーをhttp2に変更して爆速化