最大ヒープ内の値の優先順位を変更するにはどうすればよいですか？

Question

私はmax-heapを書いています。これは、優先度/値を変更することができます。しかし、私は自分のコードで何が間違っているのかを理解するのに問題があります。 私はリファレンスとして、この続いている：私は、次の実行を持っている場合は、それが何であるか...悪い結果をもたらすref これは私のコードです（私はここでの焦点それ以来、いくつかの機能がありません隠している）

static void swap(MAX_HEAP *heap, int i, int j); 
static void swim(MAX_HEAP *heap, int k); 
static void sink(MAX_HEAP *heap, int k); 

void swap(MAX_HEAP *heap, int i, int j) { 
    HEAP_ELEM s; 
    int k; 

    s = heap->binary_heap[i]; 
    k = heap->keys[s.fu]; 

    heap->binary_heap[i] = heap->binary_heap[j]; 
    heap->keys[k] = heap->keys[heap->binary_heap[j].fu]; 

    heap->keys[heap->binary_heap[j].fu] = k; 
    heap->binary_heap[j] = s; 
} 

void swim(MAX_HEAP *heap, int k) { 
    int m; 
    m = k/2.0; 
    while (k > 1 && heap->binary_heap[m].priority < heap->binary_heap[k].priority) { 
     swap(heap, k, m); 
     k = m; 
     m = k/2.0; 
    } 
} 

void sink(MAX_HEAP *heap, int k) { 
    int j; 
    while (2 * k <= heap->n) { 
     j = 2 * k; 
     if (j < heap->n && heap->binary_heap[j].priority < heap->binary_heap[j + 1].priority) 
      j++; 
     if (!(heap->binary_heap[k].priority < heap->binary_heap[j].priority)) 
      break; 
     swap(heap, k, j); 
     k = j; 
    } 
} 

MAX_HEAP *create_maxheap(int capacity) { 
    int i; 

    MAX_HEAP *ret; 
    ret = (MAX_HEAP*) malloc(sizeof (MAX_HEAP)); 
    ret->n = 0; 
    ret->binary_heap = (HEAP_ELEM*) malloc(sizeof (HEAP_ELEM) * (capacity + 1)); 
    ret->binary_heap[0].fu = 0; 
    ret->binary_heap[0].priority = 0; 
    ret->max = capacity; 

    ret->keys = (int*) malloc(sizeof (int) * (capacity + 1)); 
    for (i = 0; i <= capacity + 1; i++) { 
     ret->keys[i] = -1; 
    } 

    return ret; 
} 

HEAP_ELEM get_maxheap(MAX_HEAP *heap) { 
    HEAP_ELEM ret; 
    if (heap->n == 0) { 
     return; 
    } 
    ret = heap->binary_heap[1]; 

    heap->keys[ret.fu] = -1; 

    swap(heap, 1, heap->n); 
    heap->n--; 
    sink(heap, 1); 

    return ret; 
} 

void insert_maxheap(MAX_HEAP *heap, int fu, int p) { 
    if (heap->n + 1 >= heap->max) { 
     int i; 
     heap->max *= 2; 
     heap->keys = (int*) realloc(heap->keys, sizeof (int) * (heap->max + 1)); 
     heap->binary_heap = (HEAP_ELEM*) realloc(heap->binary_heap, sizeof (HEAP_ELEM) * (heap->max + 1)); 
     for (i = heap->n+1; i < heap->max + 1; i++) { 
      heap->keys[i] = -1; 
     } 
    } 

    heap->n++; 
    heap->binary_heap[heap->n].fu = fu; 
    heap->binary_heap[heap->n].priority = p; 
    heap->keys[fu] = heap->n; 
    swim(heap, heap->n); 
} 

void modify_maxheap(MAX_HEAP *heap, int fu, int p) { 
    int i; 
    i = heap->keys[fu]; 
    int old; 

    if (i == -1) { 
     insert_maxheap(heap, fu, p); 
     return; 
    } 

    old = heap->binary_heap[i].priority; 

    heap->binary_heap[i].fu = fu; 
    heap->binary_heap[i].priority = p; 
    heap->keys[fu] = i; 

    if (old < p) { 
     /* we need to bubble up*/ 
     swim(heap, i); 
    } else if (old > p) { 
     //we need to bubble down 
     sink(heap, i); 
    } 
} 

をここで間違っている？私は主キーとして「FU」を持っているHEAP_ELEM（の位置を知っているし、その優先順位を変更するためにHEAP_ELEMのインデックスを格納する配列を使用しています。例えば...

int main(int argc, char** argv) { 
    MAX_HEAP *heap, *heap2; 
    HEAP_ELEM he; 
    heap = create_maxheap(3); 

    modify_maxheap(heap, 1, 7); 
    modify_maxheap(heap, 2, 10); 
    modify_maxheap(heap, 3, 78); 
    modify_maxheap(heap, 4, 3); 
    modify_maxheap(heap, 5, 45); 

    printf("heap 1\n\n"); 
    while(heap->n > 0) { 
     he = get_maxheap(heap); 
     printf("..fu: %d; value: %d\n", he.fu, he.priority); 
    } 
    printf("max size of heap1: %d\n", heap->max); 
    printf("\n\n"); 

    heap2 = create_maxheap(10); 

    modify_maxheap(heap2, 3, 90); 
    modify_maxheap(heap2, 1, 7);  
    modify_maxheap(heap2, 2, 10); 
    modify_maxheap(heap2, 3, 9); 
    modify_maxheap(heap2, 3, 92); 
    modify_maxheap(heap2, 4, 3); 
    modify_maxheap(heap2, 3, 90); 
    modify_maxheap(heap2, 1, 99); 
    modify_maxheap(heap2, 5, 45); 
    modify_maxheap(heap2, 1, 89); 

    printf("heap 2\n\n"); 
    while(heap2->n > 0) { 
     he = get_maxheap(heap2); 
     printf("fu: %d; value: %d\n", he.fu, he.priority); 
    } 


    return (EXIT_SUCCESS); 
} 

注。この私の出力です：

heap 1 

..fu: 3; value: 78 
..fu: 5; value: 45 
..fu: 2; value: 10 
..fu: 1; value: 7 
..fu: 4; value: 3 
max size of heap1: 6 


heap 2 

fu: 1; value: 99 
fu: 3; value: 90 
fu: 1; value: 89 
fu: 5; value: 45 
fu: 4; value: 3 

Answer 1

私はmodify_maxheap機能を変更しているし、それが働いた：

void modify_maxheap(MAX_HEAP *heap, int fu, int p) { 
    int i; 
    i = heap->keys[fu]; 

    if (i == -1) { 
     insert_maxheap(heap, fu, p); 
     return; 
    }  

    heap->binary_heap[i].priority = p; 
    swim(heap, i); 
    sink(heap, i); 
} 

理由は、我々が保証にいかなる変更の場合はバブルアップとバブルダウンに持っているということですヒープの状態私はそれが誰かの拠点として役立つことを願っています。