堆的C语言实现

在C++中,可以通过std::priority_queue来使用堆。

堆的C语言实现:

heap.c

/** @file heap.c
* @brief 堆,默认为小根堆,即堆顶为最小.
*/
#include <stdlib.h> /* for malloc() */
#include <string.h> /* for memcpy() */
typedef int heap_elem_t; // 元素的类型

/**
* @struct
* @brief 堆的结构体
*/
typedef struct heap_t
{
  int size;  /** 实际元素个数 */
  int capacity;   /** 容量,以元素为单位 */
  heap_elem_t *elems;  /** 堆的数组 */
  int (*cmp)(const heap_elem_t*, const heap_elem_t*);
}heap_t;

/** 元素的比较函数 */
/** 基本类型(如 int, long, float, double)的比较函数 */
int cmp_int(const int *x, const int *y)
{
  const int sub = *x - *y;
  if(sub > 0)
  {
    return 1;
  }
  else if(sub < 0)
  {
    return -1;
  }
  else
  {
    return 0;
  }
}

/**
* @brief 堆的初始化.
* @param[out] h 堆对象的指针
* @param[out] capacity 初始容量
* @param[in] cmp cmp 比较函数,小于返回-1,等于返回 0
* 大于返回 1,反过来则是大根堆
* @return 成功返回 0,失败返回错误码
*/
int heap_init(heap_t *h, const int capacity, int (*cmp)(const heap_elem_t*, const heap_elem_t*))
{
  h->size = 0;
  h->capacity = capacity;
  h->elems = (heap_elem_t*)malloc(capacity * sizeof(heap_elem_t));
  h->cmp = cmp;
  return 0;
}

/**
* @brief 释放堆.
* @param[inout] h 堆对象的指针
* @return 成功返回 0,失败返回错误码
*/
int heap_uninit(heap_t *h)
{
  h->size = 0;
  h->capacity = 0;
  free(h->elems);
  h->elems = NULL;
  h->cmp = NULL;
  return 0;
}

/**
* @brief 判断堆是否为空.
* @param[in] h 堆对象的指针
* @return 是空,返回 1,否则返回 0
*/
int heap_empty(const heap_t *h)
{
  return h->size == 0;
}

/**
* @brief 获取元素个数.
* @param[in] s 堆对象的指针
* @return 元素个数
*/
int heap_size(const heap_t *h)
{
  return h->size;
}

/*
* @brief 小根堆的自上向下筛选算法.
* @param[in] h 堆对象的指针
* @param[in] start 开始结点
* @return 无
*/
void heap_sift_down(const heap_t *h, const int start)
{
  int i = start;
  int j;
  const heap_elem_t tmp = h->elems[start];
  for(j = 2 * i + 1; j < h->size; j = 2 * j + 1)
  {
    if(j < (h->size - 1) && h->cmp(&(h->elems[j]), &(h->elems[j + 1])) > 0)
    {
      j++; /* j 指向两子女中小者 */
    }
    // tmp <= h->data[j]
    if(h->cmp(&tmp, &(h->elems[j])) <= 0)
    {
      break;
    }
    else
    {
      h->elems[i] = h->elems[j];
      i = j;
    }
  }
  h->elems[i] = tmp;
}

/*
* @brief 小根堆的自下向上筛选算法.
* @param[in] h 堆对象的指针
* @param[in] start 开始结点
* @return 无
*/
void heap_sift_up(const heap_t *h, const int start)
{
  int j = start;
  int i= (j - 1) / 2;
  const heap_elem_t tmp = h->elems[start];
  
  while(j > 0)
  {
    // h->data[i] <= tmp
    if(h->cmp(&(h->elems[i]), &tmp) <= 0)
    {
      break;
    }
    else
    {
      h->elems[j] = h->elems[i];
      j = i;
      i = (i - 1) / 2;
    }
  }
  h->elems[j] = tmp;
}

/**
* @brief 添加一个元素.
* @param[in] h 堆对象的指针
* @param[in] x 要添加的元素
* @return 无
*/
void heap_push(heap_t *h, const heap_elem_t x)
{
  if(h->size == h->capacity)
  {
    /* 已满,重新分配内存 */
    heap_elem_t* tmp = (heap_elem_t*)realloc(h->elems, h->capacity * 2 * sizeof(heap_elem_t));
    h->elems = tmp;
    h->capacity *= 2;
  }
  h->elems[h->size] = x;
  h->size++;
  heap_sift_up(h, h->size - 1);
}

/**
* @brief 弹出堆顶元素.
* @param[in] h 堆对象的指针
* @return 无
*/
void heap_pop(heap_t *h)
{
  h->elems[0] = h->elems[h->size - 1];
  h->size --;
  heap_sift_down(h, 0);
}

/**
* @brief 获取堆顶元素.
* @param[in] h 堆对象的指针
* @return 堆顶元素
*/
heap_elem_t heap_top(const heap_t *h)
{
  return h->elems[0];
}

相关推荐