二叉堆的C语言实现
堆是一颗完全树，同时满足每个节点均大于或小于它的子节点，这样的数据结构被称为最大堆或者最小堆。 这种结构处于一种半排序状态，它的存取效率从整体上讲介于有序和无序之间。当对象处于动态时，是种非常有优势的数据结构。存取的时间复杂为log(a,n),其中a为完全树的度。
通常二叉堆以数组存储，层为 log(2,n)，可以使用以下的代码来定义二叉堆结构。
typedef struct binary_heap_s* binary_heap_pt;
typedef struct binary_heap_s {
int size;
int current;
Item *data;
} binary_heap_t;
当以数组存储时，二叉堆的父子节点下标存在如下关系。
第一个元素索引为0:
- 索引为i的左孩子的索引是 (2*i+1);
- 索引为i的右孩子的索引是 (2*i+2);
- 索引为i的父结点的索引是 floor((i-1)/2);
第一个元素索引为1:
- 索引为i的左孩子的索引是 (2*i);
- 索引为i的右孩子的索引是 (2*i+1);
- 索引为i的父结点的索引是 floor(i/2);
以下代码都按第一个元素索引为0方式
添加元素图解
在堆中添加元素时需要执行向上堆化操作，假设在最小堆中添加35，需要执行以下步骤。
代码实现如下：
/*
* Name: fixup
* Description: 向上堆化
*
*/
static void
fixup(binary_heap_pt heap, int k)
{
while (k>0 && item_cmp(heap->data[(k - 1) / 2],heap->data[k])) {
swap(heap->data, k, (k - 1) / 2);
k = (k - 1) / 2;
}
}
int
binary_heap_push(binary_heap_pt heap, Item element)
{
if (heap == NULL) {
return 0;
}
if (heap->current == heap->size) {
return 0;
}
heap->data[heap->current] = element;
fixup(heap, heap->current++);
return 1;
}
删除堆顶元素图解
在堆中移除堆顶元素时需要执行向下堆化操作，假设在最小堆中移除堆顶完素，需要执行以下步骤。
代码实现如下：
/*
* Name: fixdown
* Description: 向下堆化
*
*/
static void
fixdown(binary_heap_pt heap, int k, int end)
{
int temp;
while (k*2 + 1 <= end) {
temp = k*2 + 1;
if (temp < end && item_cmp(heap->data[temp], heap->data[temp + 1])) {
temp++;
}
if (!item_cmp(heap->data[k], heap->data[temp])) {
break;
}
swap(heap->data, k, temp);
k = temp;
}
}
Item
binary_heap_pop(binary_heap_pt heap)
{
swap(heap->data, 0, heap->current - 1);
fixdown(heap, 0, heap->current - 2);
return heap->data[--heap->current];
}
完整源码
/* binary_heap.h */
#ifndef BINARY_HEAP_H
#define BINARY_HEAP_H
typedef int Item;
typedef struct binary_heap_s* binary_heap_pt;
typedef struct binary_heap_s {
int size;
int current;
Item *data;
} binary_heap_t;
binary_heap_pt binary_heap_init(int size);
void binary_heap_free(binary_heap_pt heap);
void binary_heap_print(binary_heap_pt heap);
int binary_heap_push(binary_heap_pt heap, Item element);
Item binary_heap_pop(binary_heap_pt heap);
Item binary_heap_top(binary_heap_pt heap);
int binary_heap_empty(binary_heap_pt heap);
#endif
binary_heap.h
/* binary_heap.c */
/*
* =====================================================================================
*
* Filename: binary_heap.c
*
* Description: 二叉堆实现
*
* Version: 1.0
* Created: 2016-09-19 20:08
* Revision: none
* Compiler: gcc
*
* Author: simon
*
* =====================================================================================
*/
#include <stdio.h>
#include <stdlib.h>
#include "binary_heap.h"
static void
swap(Item *data, int a, int b)
{
Item c;
c = data[a];
data[a] = data[b];
data[b] = c;
}
/*
* 最小堆 ((a) > (b))
* 最大堆 ({a} < (b))
*
*/
#define item_cmp(a, b) ((a) > (b)) /* 最小堆 */
/*
* Name: fixup
* Description: 向上堆化
*
*/
static void
fixup(binary_heap_pt heap, int k)
{
while (k>0 && item_cmp(heap->data[(k - 1) / 2],heap->data[k])) {
swap(heap->data, k, (k - 1) / 2);
k = (k - 1) / 2;
}
}
/*
* Name: fixdown
* Description: 向下堆化
*
*/
static void
fixdown(binary_heap_pt heap, int k, int end)
{
int temp;
while (k*2 + 1 <= end) {
temp = k*2 + 1;
if (temp < end && item_cmp(heap->data[temp], heap->data[temp + 1])) {
temp++;
}
if (!item_cmp(heap->data[k], heap->data[temp])) {
break;
}
swap(heap->data, k, temp);
k = temp;
}
}
binary_heap_pt
binary_heap_init(int size)
{
if (size<=0) {
return NULL;
}
binary_heap_pt heap_pt = malloc(sizeof(binary_heap_t));
heap_pt->data = malloc(sizeof(Item)*size);
heap_pt->size = size;
heap_pt->current = 0;
return heap_pt;
}
void
binary_heap_free(binary_heap_pt heap)
{
if (heap == NULL) {
return;
}
free(heap->data);
free(heap);
}
void
binary_heap_print(binary_heap_pt heap)
{
int i;
if (heap == NULL) {
return;
}
for (i=0; i<heap->size; i++) {
printf("%d ", heap->data[i]);
}
}
int
binary_heap_push(binary_heap_pt heap, Item element)
{
if (heap == NULL) {
return 0;
}
if (heap->current == heap->size) {
return 0;
}
heap->data[heap->current] = element;
fixup(heap, heap->current++);
return 1;
}
Item
binary_heap_pop(binary_heap_pt heap)
{
swap(heap->data, 0, heap->current - 1);
fixdown(heap, 0, heap->current - 2);
return heap->data[--heap->current];
}
Item
binary_heap_top(binary_heap_pt heap)
{
return heap->data[0];
}
int
binary_heap_empty(binary_heap_pt heap)
{
return heap->current == 0;
}
binary_heap.c
/* binary_heap_test.c */
#include <stdlib.h>
#include <stdio.h>
#include "binary_heap.h"
#define LENGTH(a) ( (sizeof(a)) / (sizeof(a[0])) )
int
main(int argc, char *argv[])
{
int a[] = {10, 40, 30, 60, 90, 70, 20, 50, 80};
int i, len=LENGTH(a);
binary_heap_pt heap = NULL;
heap = binary_heap_init(LENGTH(a) + 10);
printf("\n== 空堆检查: %d", binary_heap_empty(heap));
printf("\n== 插入数据: ");
for(i=0; i<len; i++)
{
printf("%d ", a[i]);
binary_heap_push(heap, a[i]);
}
printf("\n== 空堆检查: %d", binary_heap_empty(heap));
printf("\n== 最 小 堆: ");
binary_heap_print(heap);
i=35;
binary_heap_push(heap, i);
printf("\n== 添加元素: %d", i);
printf("\n== 最 小 堆: ");
binary_heap_print(heap);
printf("\n== 堆顶元素: %d\n", binary_heap_top(heap));
i = binary_heap_pop(heap);
printf("\n== 删除元素: %d", i);
printf("\n== 最 小 堆: ");
binary_heap_print(heap);
printf("\n");
i = binary_heap_pop(heap);
printf("\n== 删除元素: %d", i);
printf("\n== 最 小 堆: ");
binary_heap_print(heap);
printf("\n");
binary_heap_free(heap);
return 0;
}
binary_heap_test.c
测试程序的运行结果
== 空堆检查: 1
== 插入数据: 10 40 30 60 90 70 20 50 80
== 空堆检查: 0
== 最 小 堆: 10 40 20 50 90 70 30 60 80 0 0 0 0 0 0 0 0 0 0
== 添加元素: 35
== 最 小 堆: 10 35 20 50 40 70 30 60 80 90 0 0 0 0 0 0 0 0 0
== 堆顶元素: 10
== 删除元素: 10
== 最 小 堆: 20 35 30 50 40 70 90 60 80 10 0 0 0 0 0 0 0 0 0
== 删除元素: 20
== 最 小 堆: 30 35 70 50 40 80 90 60 20 10 0 0 0 0 0 0 0 0 0
转载文章请注明出处： http://mingnote.com