#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
typedef int HeapDataType;
typedef struct Heap
{
  HeapDataType* a;
  int sz;
  int capacity;
}Heap;
void HeapInit(Heap* php);
void HeapPush(Heap* php, HeapDataType x);
void HeapPop(Heap* php);
HeapDataType HeapTop(Heap* php);
int HeapSize(Heap* php);
bool HeapEmpty(Heap* php);
void HeapDestroy(Heap* php);
void HeapPrint(Heap* php);
void AdjustDown(int* a, int parent, int sz);
void AdjustUp(int* a, int child);
void Swap(HeapDataType* p1, HeapDataType* p2);
void HeapInit(Heap* php)
{
  assert(php);
  php->a = NULL;
  php->capacity = php->sz = 0;
}
void Swap(HeapDataType* p1, HeapDataType* p2)
{
  HeapDataType tmp = *p1;
  *p1 = *p2;
  *p2 = tmp;
}
void AdjustUp(int* a, int child)
{
  assert(a);
  int parent = (child - 1) / 2;
  while (child>0)//用parent>=0也行，只是这样的话就不是正常结束的了
  {
    if (a[child] < a[parent])
    {
      Swap(&a[child], &a[parent]);
      child = parent;
      parent = (child - 1) / 2;
    }
    else
      break;
  }
}
void HeapPush(Heap* php, HeapDataType x)
{
  assert(php);
  if (php->capacity == php->sz)
  {
    int newcapacity = php->a == NULL ? 4 : php->capacity * 2;
    HeapDataType* tmp = (HeapDataType*)realloc(php->a, sizeof(HeapDataType) * newcapacity);
    if (tmp == NULL)
    {
      perror("realloc fail:");
      exit(-1);
    }
    php->a = tmp;
    php->capacity = newcapacity;
  }
  php->a[php->sz] = x;
  php->sz++;
  //向上调整算法，保证建立的是堆（这里以建小堆为例）
  AdjustUp(php->a, php->sz - 1);//第二个参数传的是push这个数据的下标
}
void AdjustDown(int* a, int parent, int sz)
{
  assert(a);
  int child = parent * 2 + 1;
  while (child < sz)
  {
    if (child + 1 < sz && a[child + 1] > a[child])
      child++;
    if (a[child] > a[parent])
    {
      Swap(&a[child], &a[parent]);
      parent = child;
      child = parent * 2 + 1;
    }
    else
      break;
  }
}
void HeapPop(Heap* php)
{
  assert(php);
  assert(php->sz > 0);
  //假设建小堆，要pop掉最小的一个数值（堆顶），要让下面的结构继续保持小堆结构就不能只将数据向前挪动一位，
  //否则堆的结构将会被破坏。正确做法是将堆顶的数据与最后一个数据交换，然后重新向下建堆，再pop掉堆尾数据。
  Swap(&php->a[0], &php->a[php->sz - 1]);
  php->sz--;
  AdjustDown(php->a, 0, php->sz);
}
HeapDataType HeapTop(Heap* php)
{
  assert(php);
  assert(php->sz > 0);
  return php->a[0];
}
int HeapSize(Heap* php)
{
  assert(php);
  return php->sz;
}
bool HeapEmpty(Heap* php)
{
  assert(php);
  return php->sz == 0;
}
void HeapDestroy(Heap* php)
{
  assert(php);
  free(php->a);
  php->capacity = php->sz = 0;
}
void HeapPrint(Heap* php)
{
  assert(php);
  for (int i = 0; i < php->sz; i++)
  {
    printf("%d ", php->a[i]);
  }
  printf("\n");
}

void HeapSort(HeapDataType* a, int sz)
{
  //从最后一个结点的父亲开始建堆
  for (int i = (sz - 1 - 1) / 2; i >= 0; i--)
  {
    AdjustDown(a, i, sz);
  }
  for (int i = sz-1; i>0; i--)
  {
    Swap(&a[0], &a[i]);
    AdjustDown(a, 0, --sz);
  }
}

    //建立一个k个数的小堆，依次遍历数组，比堆顶元素大就替换，然后向下调整,最后堆中数据就是topk
  //时间复杂度为：N+N*logk  空间复杂度为O(k)
  int topk[5] = {0};
  int i;
  for (i = 0; i < 5; i++)
  {
    topk[i] = array[i];
  }
  //建小堆
  for (i = (5 - 1 - 1) / 2; i >= 0; i--)
  {
    AdjustDown(topk, i, 5);
  }
  //遍历替换
  for (i=5; i < sz; i++)
  {
    if (array[i] > topk[0])
    {
      topk[0] = array[i];
      AdjustDown(topk, 0, 5);
    }
  }
  for (i = 0; i < 5; i++)
    printf("%d ", topk[i]);
  //这种方法占据内存较小，比较优秀