堆排序+TopK问题——“数据结构与算法”

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int HeapDataType;
typedef struct Heap
{
  HeapDataType* a;
  int size;
  int capacity;
}Heap;
//堆的初始化
void HeapInit(Heap* php);
//堆的销毁
void HeapDestroy(Heap* php);
//插入数据
void HeapPush(Heap* php, HeapDataType x);
//向上调整算法
void AdjustUp(HeapDataType* a, int child);
//删除堆顶数据
void HeapPop(Heap* php);
//向下调整算法
void AdjustDown(int* a, int n, int parent);
//判空
bool HeapEmpty(Heap* php);
//堆顶元素
HeapDataType HeapTop(Heap* php);
//元素个数
int HeapSize(Heap* php);

#include"heap.h"
//堆的初始化
void HeapInit(Heap* php)
{
  assert(php);
  php->a = NULL;
  php->size = 0;
  php->capacity = 0;
}
//堆的销毁
void HeapDestroy(Heap* php)
{
  assert(php);
  free(php->a);
  php->a = NULL;
  php->size = 0;
  php->capacity = 0;
}
//交换数据
void Swap(HeapDataType* p1, HeapDataType* p2)
{
  HeapDataType tmp = *p1;
  *p1 = *p2;
  *p2 = tmp;
}
//向上调整算法
void AdjustUp(HeapDataType* a, int child)
{
  int parent = (child - 1) / 2;
  while (child > 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->size == php->capacity)
  {
    int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
    HeapDataType* tmp = (HeapDataType*)realloc(php->a, newcapacity * sizeof(HeapDataType));
    if (tmp == NULL)
    {
      perror("realloc fail");
      return;
    }
    php->a = tmp;
    php->capacity = newcapacity;
  }
  php->a[php->size] = x;
  php->size++;
  AdjustUp(php->a, php->size - 1);
}
//向下调整算法
//这边写int* 而不写HeapDataType* 是有意为之的 为以后堆排序作准备
void AdjustDown(int* a, int n, int parent)
{
  //默认左孩子小
  int child = parent * 2 + 1;
  while (child < n)//孩子在数组范围内
  {
    //选出左右孩子中小/大的那一个
    //有可能假设错了
    //左孩子不存在，一定没有右孩子——完全二叉树
    //左孩子存在，有可能没有右孩子
    if ( child + 1 < n && a[child + 1] < a[child])
    //  右孩子存在     右孩子<左孩子
    //不能这么写 if (la[child + 1] < a[chid] && child + 1 < n )
    //这样写会有越界的风险 因为是先访问了数组中的元素 再去比较右孩子是否存在
    {
      ++child;
    }
    //child就是小的那个孩子
    //不关心到底是左孩子还是右孩子 小根堆：和小的孩子比较就可以了
    if (a[child] < a[parent])
    {
      Swap(&a[child], &a[parent]);
      child = parent;
      child = parent * 2 + 1;//默认又算的是左孩子
    }
    else
    {
      break;
    }
 
  }
}
//判空
bool HeapEmpty(Heap* php)
{
  assert(php);
  if (php->size == 0)
  {
    return true;
  }
  else
  {
    return false;
  }
}
//删除堆顶数据
void HeapPop(Heap* php)
{
  assert(php);
  assert(!HeapEmpty(php));
  Swap(&php->a[0], &php->a[php->size - 1]);
  php->size--;
  AdjustDown(php->a, php->size, 0);
}
//堆顶元素
HeapDataType HeapTop(Heap* php)
{
  assert(php);
  assert(!HeapEmpty(php));
  return php->a[0];
}
//元素个数
int HeapSize(Heap* php)
{
  assert(php);
  return php->size;
}

void HeapSort(int* a, int n)
{
  Heap hp;
  HeapInit(&hp);
  int i = 0;
  for (i = 0; i < n; i++)
  {
    HeapPush(&hp, a[i]);
  }
  while (!HeapEmpty(&hp))
  {
    int top = HeapTop(&hp);
    a[i++] = top;
    HeapPop(&hp);
  }
  HeapDestroy(&hp);
}
int main()
{
  int a[] = { 7,8,3,5,1,9,5,4 };
  int sz = sizeof(a) / sizeof(a[0]);
  HeapSort(a, sz);
  return 0;
}

//建堆——向上调整建堆
int i = 0;
for (i = 1; i < n; i++)
{
  AdjustUp(a, i);
}

void HeapSort(int* a, int n)
{
  //建堆——向上调整建堆
  int i = 0;
  for (i = 1; i < n; i++)
  {
    AdjustUp(a, i);
  }
  //升序——建大堆
  //降序——建小堆
  int end = n - 1;
  while (end > 0)
  {
    Swap(&a[0], &a[end]);
    AdjustDown(a, end, 0);
    --end;
  }
}

//建堆——向下调整建堆
int i = 0;
for (i = (n - 1 - 1) / 2; i >= 0; i--)
{
  AdjustDown(a, n, i);
}

void HeapSort(int* a, int n)
{
    //建堆——向下调整建堆
  int i = 0;
  for (i = (n - 1 - 1) / 2; i >= 0; i--)
  {
    AdjustDown(a, n, i);
  }
  //升序——建大堆
  //降序——建小堆
  int end = n - 1;
  while (end > 0)
  {
    Swap(&a[0], &a[end]);
    AdjustDown(a, end, 0);
    --end;
  }
}

void CreateNDate()
{
  // 造数据
  int n = 10000;
  srand(time(0));
  const char* file = "data.txt";
  FILE* fin = fopen(file, "w");
  if (fin == NULL)
  {
    perror("fopen error");
    return;
  }
  for (size_t i = 0; i < n; ++i)
  {
    int x = rand() % 1000000;
    fprintf(fin, "%d\n", x);
  }
  fclose(fin);
}

void PrintTopK(int k)
{
  const char* file = "data.txt";
  FILE* fout = fopen(file, "r");
  if (fout == NULL)
  {
    perror("fopen error");
    return;
  }
  int* kminheap = (int*)malloc(sizeof(int) * k);
  if (kminheap == NULL)
  {
    perror("malloc error");
    return;
  }
  for (int i = 0; i < k; i++)
  {
    fscanf(fout, "%d", &kminheap[i]);
  }
  // 建小堆
  for (int i = (k - 1 - 1) / 2; i >= 0; i--)
  {
    AdjustDown(kminheap, k, i);
  }
  int val = 0;
  while (!feof(fout))
  {
    fscanf(fout, "%d", &val);
    if (val > kminheap[0])
    {
      kminheap[0] = val;
      AdjustDown(kminheap, k, 0);
    }
  }
  for (int i = 0; i < k; i++)
  {
    printf("%d ", kminheap[i]);
  }
  printf("\n");
}