普通的堆排序

#include <stdio.h>
void swap(int *a, int *b) {
  int t = *a;
  *a = *b;
  *b = t;
}
//调整堆
void adjust_heap(int *heap, int s, int e) {
  for (int n;; s = n) {
    if ((n = 2 * s + 1) + 1 < e && heap[n + 1] < heap[n]) n++;
    if (n >= e || heap[s] < heap[n]) break;
    swap(heap + s, heap + n);
  }
}
//O(n) 建堆
void create_heap(int *arr, int size) {
  for (int i = (size - 2) / 2; ~i; i--) adjust_heap(arr, i, size);
}
//弹出堆
int pop_heap(int *heap, int *size) {
  swap(heap, heap + (--*size));
  adjust_heap(heap, 0, *size);
  return heap[*size];
}
// 插入堆
void push_heap(int *heap, int *size, int val) {
  heap[(*size)++] = val;
  for (int i = (*size - 2) / 2; i; i = (i - 1) / 2) adjust_heap(heap, i, *size);
  adjust_heap(heap, 0, *size);
}
int main() {
  int arr[] = {4, 745, 6, 8, 2, 4, 48, 85, 2, 78, 99};
  int l = sizeof(arr) / sizeof(int);
  create_heap(arr, l);
  while (l) printf("\n%d", pop_heap(arr, &l));
  return 0;
}

这个优先队列,或堆排序很简洁性能也不错。但是就是不能自定义类型和，排序规则。要实现上面功能，我首先想到的是宏，虽然用void 指针和函数指针似乎也可以实现。

#include <stdio.h>

#define SWAP(T, a, b) \
  do {                \
    T c = a;          \
    a = b;            \
    b = c;            \
  } while (0)

#define ADJUST_HEAP(T, heap, S, E, cmp)                              \
  do {                                                               \
    for (int n, s = S;; s = n) {                                     \
      if ((n = 2 * s + 1) + 1 < E && cmp(heap[n + 1], heap[n])) n++; \
      if (n >= E || cmp(heap[s], heap[n])) break;                    \
      SWAP(T, heap[s], heap[n]);                                     \
    }                                                                \
  } while (0)

#define CREATE_HEAP(T, arr, size, cmp)                                       \
  do {                                                                       \
    for (int i = (size - 2) / 2; ~i; i--) ADJUST_HEAP(T, arr, i, size, cmp); \
  } while (0)

#define POP_HEAP(T, heap, size, cmp)    \
  do {                                  \
    --size;                             \
    SWAP(T, heap[0], heap[size]);       \
    ADJUST_HEAP(T, heap, 0, size, cmp); \
  } while (0)

int bj(int a, int b) { return a < b; }

int main() {
  int arr[] = {4, 745, 6, 8, 2, 4, 48, 85, 2, 78, 99};
  int l = sizeof(arr) / sizeof(int);
  CREATE_HEAP(int, arr, l, bj);
  while (l) {
    POP_HEAP(int, arr, l, bj);
    printf("%d%c", arr[l], ","[l == 0]);
  }
  return 0;
}