学步园

/* binary_heap_for_kruskal.c -- 二叉堆实现文件 */<br /> #include <stdio.h><br /> #include <stdlib.h><br /> #include "binary_heap_for_kruskal.h"</p> <p>/* 局部函数声明 */</p> <p>static int Percolate_Up (const Binary_Heap * const pbh, const int index) ;<br /> static int Percolate_Down (const Binary_Heap * const pbh, const int index) ;</p> <p>/* 接口函数定义 */</p> <p>int Initialize_B (Binary_Heap * const pbh, const int capacity)<br /> {<br /> *pbh = (struct binary_heap *) malloc (sizeof (struct binary_heap)) ;<br /> if (NULL == *pbh)<br /> return 0 ;<br /> (*pbh) -> heap = (Edge *) malloc (sizeof (Edge) * (capacity + 1)) ;<br /> if (NULL == (*pbh) -> heap)<br /> {<br /> free (*pbh) ;<br /> return 0 ;<br /> }<br /> (*pbh) -> heap[0].weight = NEGATIVEINFINITY ;<br /> (*pbh) -> current = 0 ;<br /> (*pbh) -> capacity = capacity ;</p> <p> return 1 ;<br /> }</p> <p>int Insert_B (const Binary_Heap * const pbh, const Edge * const pd)<br /> {<br /> int current ;</p> <p> if ((*pbh) -> current == (*pbh) -> capacity)<br /> return 0 ;<br /> current = ++(*pbh) -> current ;<br /> (*pbh) -> heap[current].v_hash_value = pd -> v_hash_value ;<br /> (*pbh) -> heap[current].w_hash_value = pd -> w_hash_value ;<br /> (*pbh) -> heap[current].weight = pd -> weight ;<br /> Percolate_Up (pbh, current) ;</p> <p> return 1 ;<br /> }</p> <p>int DeleteMin_B (const Binary_Heap * const pbh, Edge * const pd)<br /> {<br /> if ((*pbh) -> current <= 0)<br /> return 0 ;<br /> *pd = (*pbh) -> heap[1] ;<br /> Percolate_Down (pbh, (*pbh) -> current) ;<br /> (*pbh) -> current-- ;</p> <p> return 1 ;<br /> }</p> <p>void Release_B (const Binary_Heap * const pbh)<br /> {<br /> free ((*pbh) -> heap) ;<br /> free (*pbh) ;<br /> }</p> <p>/* 局部函数定义 */</p> <p>static int Percolate_Up (const Binary_Heap * const pbh, const int index)<br /> {<br /> Edge temp = (*pbh) -> heap[index] ;<br /> int i ;</p> <p> if (index <= 0 || index > (*pbh) -> current)<br /> return 0 ;<br /> for (i = index; i / 2 > 0; i /= 2)<br /> {<br /> if (temp.weight < (*pbh) -> heap[i / 2].weight)<br /> (*pbh) -> heap[i] = (*pbh) -> heap[i / 2] ;<br /> else<br /> break ;<br /> }<br /> (*pbh) -> heap[i] = temp ;</p> <p> return 1 ;<br /> }</p> <p>static int Percolate_Down (const Binary_Heap * const pbh, const int index)<br /> {<br /> int current = (*pbh) -> current ;<br /> Edge temp = (*pbh) -> heap[current] ;<br /> int i, child ;</p> <p> if (index <= 0 || index > (*pbh) -> current)<br /> return 0 ;<br /> for (i = 1; i * 2 <= current; i = child)<br /> {<br /> child = i * 2 ;<br /> if (child != current && (*pbh) -> heap[child].weight > (*pbh) -> heap[child + 1].weight)<br /> child++ ;<br /> if (temp.weight > (*pbh) -> heap[child].weight)<br /> (*pbh) -> heap[i] = (*pbh) -> heap[child] ;<br /> else<br /> break ;<br /> }<br /> (*pbh) -> heap[i] = temp ;</p> <p> return 1 ;<br /> }