堆与堆排序

#pragma once
#include <stdio.h>
#include <stdlib.h>
//先构造大堆
#include <assert.h>
#include <string.h>
typedef int HPDataType;
typedef struct Heap
{
  HPDataType* _a;
  int _size;
  int _capacity;
}Heap;
int c = 7;
int* s = &c;
//向上调整算法
void AdjustUp(HPDataType* Up, int child);//我们得知道插入的位置在哪我们才能调整
//需要自定义一个向上调整算法
//向上调整算法可以建堆
void AdjustUp(HPDataType* Up, int child)//跟老师的思路一样,没问题
{
  int tmp = 0;
  int parents = (child - 1) / 2;//这样插入的前提是本身他就是个堆我们才能这么插入
  while (child)
  {
    parents = (child - 1) / 2;
    if (Up[parents] < Up[child])
    {
      tmp = Up[child];
      Up[child] = Up[parents];
      Up[parents] = tmp;
      child = parents;
    }
    else
    {
      break;
    }
  }
}
void AdjustDown(HPDataType* a, int n, int parents);//向下调整算法,可以用于删除数据
//因为我们删除数据的原理是队头数据和队尾部数据交换，然后队尾-1
//再开始执行向下调整算法(那此时这里我们有几个要注意的点就是——我们如果直接删除队头数据的话
//我们可能会打乱堆里面的整体数据顺序，而为了不打乱整体的数据顺序，所以我们
//采用交换位置的方法),然后执行向下调整算法
void AdjustDown(HPDataType* a, int n, int parents)
{
  //向下调整算法里我们得知道他的父节点，再开始进行向下调整
  //而在向下调整的时候,我们得判断两边哪个最大，我们挑最大的上场，然后在他的路径下一直判断
  //挑最大的上来能保证第一行是最大的
  //因为根据我们的前面的推论左右孩子永远比父节点小
  //所以我们如果交换后是最小的我们就把他放到左子树或右子树（放在左子树和右子树取决与第一次判断）的最下面
  //这里我们不用定义leftchild和rightchild，而是我们
  //用一种很独特的方式
  //假设定义法，我们直接去把定义一个孩子定义为最大的
  //已知左孩子公式为 2*parents+1
  //这里我们假设左孩子为最大
  int tmp = 0;//交换的容器
  int child = 2 * parents + 1;
  while (child  < n)//迭代过程，停止条件,也不能child-1<n
  //是因为我们如果child-1<n的话,如果我们的child下标时的数据<child+1时下标数据时，我们就没有去判断了
    //也就是当我们最后child下标为最后一个时，我们就少判断了一次，所以我们需要再去判断一次
  {
    //那么也就是如果child 下标小于child+1时，我们就加个条件child+1<n限制再执行child++。
    //这是为了以防越界，
    if (a[child] > a[child+1] && child+1<n)//先判断左右孩子哪个大，如果假设的孩子小，那么就++下标
      //其实就是左孩子小于右孩子，那么下标就跳到右孩子这里
       //思考为什么要加child+1<n呢，是因为我们最后child赋值后大于n的情况有三种
       //一种是赋值后在最后一个下标，，一种是赋值之后在我们给定的下标外面（这个我们已经确定好条件了
       // 就是我们child<n）
       //但是我们每次迭代后又要判断
    {
      ++child;
    }
    if (a[parents] > a[child])
    {
      tmp = a[parents];
      a[parents] = a[child];
      a[child] = tmp;
      parents = child;
      child = 2 * parents + 1;
    }
    else
    {
      break;
    }
  }
}
void AdjustDown1(HPDataType* a, int n, int parents);//向下调整算法,可以用于删除数据
//因为我们删除数据的原理是队头数据和队尾部数据交换，然后队尾-1
//再开始执行向下调整算法(那此时这里我们有几个要注意的点就是——我们如果直接删除队头数据的话
//我们可能会打乱堆里面的整体数据顺序，而为了不打乱整体的数据顺序，所以我们
//采用交换位置的方法),然后执行向下调整算法
void AdjustDown1(HPDataType* a, int n, int parents)//调整数组里的值,小根堆
{
  //向下调整算法里我们得知道他的父节点，再开始进行向下调整
  //而在向下调整的时候,我们得判断两边哪个最大，我们挑最大的上场，然后在他的路径下一直判断
  //挑最大的上来能保证第一行是最大的
  //因为根据我们的前面的推论左右孩子永远比父节点小
  //所以我们如果交换后是最小的我们就把他放到左子树或右子树（放在左子树和右子树取决与第一次判断）的最下面
  //这里我们不用定义leftchild和rightchild，而是我们
  //用一种很独特的方式
  //假设定义法，我们直接去把定义一个孩子定义为最大的
  //已知左孩子公式为 2*parents+1
  //这里我们假设左孩子为最大
  int tmp = 0;//交换的容器
  int child = 2 * parents + 2;
  while (child-1 < n)//迭代过程，停止条件
  {
    if (a[child] > a[child-1])//先判断左右孩子哪个大，如果假设的孩子小，那么就++下标
      //其实就是左孩子小于右孩子，那么下标就跳到右孩子这里
    {
      child--;
    }
    if (a[parents] < a[child])
    {
      break;
    }
    else
    {
      tmp = a[parents];
      a[parents] = a[child];
      a[child] = tmp;
      parents = child;
      child = 2 * parents + 1;
    }
  }
}
// 堆的构建
void HeapCreate(Heap* hp, HPDataType* a, int n);
void HeapCreate(Heap* hp, HPDataType* a, int n)
{
  hp->_a = (HPDataType*)malloc(sizeof(HPDataType) * n);
  hp->_capacity = n;
  hp->_size = n;
  if (hp->_a == NULL)
  {
    perror("malloc fail\n");
    exit(-1);
  }
  int i = 0;
  //while (i<n)//这样构建效率很低
  //{
  //  HeapPush(hp, a[i]);
  //  i++;
  //}
  for (int i = (n - 1 - 1) / 2; i >= 0; --i)//修改数组的值，我们利用堆进行
  {
    AdjustDown(a, n, i);
  }
  memcpy(hp->_a, a, sizeof(HPDataType) * n);//用内存函数去把数组这些里面的内存拷贝到hp_a
  // 建堆算法
}
void swap(Heap* hp);//删除的时候为了不改变顺序而交换
void swap(Heap* hp)
{
  assert(hp);
  assert(hp->_size > 0);
  int tmp = 0;
  tmp = hp->_a[0];
  hp->_a[0] = hp->_a[hp->_size - 1]; 
  hp->_a[hp->_size - 1] = tmp;
  return;
}
// 堆的销毁
void HeapDestory(Heap* hp);
void HeapDestory(Heap* hp)
{
  hp->_size = hp->_capacity = 0;
  free(hp->_a);
  free(hp);
}
// 堆的插入
//我们把堆看成一个完全二叉树，每次的插入必定有一个父节点
//1.所以我们可以根据堆的父节点公式推出父节点，并且我们现在实现的是大堆，所以每次插入时要去比对
//堆的插入是
void HeapPush(Heap* hp, HPDataType x);
void HeapPush(Heap* hp, HPDataType x)//这里我们只需要调整一条祖先路径就行
//我们的堆不是栈，我们的堆只要确保他的父节点比他的孩子节点大就行//没问题
{
  //第一种方法
  if (hp->_capacity == hp->_size)
  {
    ++hp->_capacity;
    HPDataType* ptr = (HPDataType*)realloc(hp->_a, sizeof(HPDataType) * hp->_capacity);
    if (ptr == NULL)
    {
      perror(" malloc fail ");
      exit(-1);
    }
    hp->_a = ptr;
  }
  int child = hp->_size;
  hp->_a[hp->_size++] = x;
  AdjustUp(hp->_a,child);
}
// 堆的删除
void HeapPop(Heap* hp);//删除之后要维持这个大根堆
//堆的删除要注意，是因为我们如果直接删除堆顶的话
//那么我们可能就会所有节点的顺序就会变了
//所以堆的删除我们可以最后一个和第一个互换位置
//然后size--，我们在看看交换后是不是比他左右孩子大
//如果不是就挑最大的上来,挑最大的上来能保证第一行是最大的
//因为根据我们的前面的推论左右孩子永远比父节点小
//所以我们如果交换后是最小的我们就把他放到左子树或右子树（放在左子树和右子树取决与第一次判断）的最下面
void HeapPop(Heap* hp)
{
    assert(hp);
  assert(hp->_size > 0);
  swap(hp);
  //此时是我们已知父亲节点
  //求孩子节点
  //求孩子节点的公式就是
  //int child = 0;
  //int parents = 0;
  //int tmp = 0;
  //int leftchild = 2 * parents + 1;
  //int rightchild = 2 * parents + 2;
  //while ((leftchild = 2 * parents + 1) < hp->_size - 1 && (rightchild = 2 * parents + 2) < hp->_size - 1)//想一想我们应该以什么截止呢，是child还是parents
  //{
  //  /*leftchild = 2 * parents + 1;
  //  rightchild = 2 * parents + 2;*/
  //  if (hp->_a[parents] >= hp->_a[rightchild] && hp->_a[parents] < hp->_a[leftchild])
  //  {
  //    tmp = hp->_a[leftchild];
  //    hp->_a[leftchild] = hp->_a[parents];
  //    hp->_a[parents] = tmp;
  //    parents = leftchild;
  //  }
  //  else if (hp->_a[parents] < hp->_a[rightchild] && hp->_a[parents] >= hp->_a[leftchild])
  //  {
  //    tmp = hp->_a[rightchild];
  //    hp->_a[rightchild] = hp->_a[parents];
  //    hp->_a[parents] = tmp;
  //    parents = rightchild;
  //  }
  //  else if (hp->_a[parents] < hp->_a[rightchild] && hp->_a[parents] < hp->_a[leftchild])
  //  {
  //    if (hp->_a[rightchild] >= hp->_a[leftchild])
  //    {
  //      tmp = hp->_a[rightchild];
  //      hp->_a[rightchild] = hp->_a[parents];
  //      hp->_a[parents] = tmp;
  //      parents = rightchild;
  //    }
  //    else
  //    {
  //      tmp = hp->_a[leftchild];
  //      hp->_a[leftchild] = hp->_a[parents];
  //      hp->_a[parents] = tmp;
  //      parents = leftchild;
  //    }
  //  }
  //  else
  //  {
  //    break;
  //  }
  //}
  hp->_size--;
  int parents = 0;
  AdjustDown(hp->_a, hp->_size, parents);
}
// 取堆顶的数据
HPDataType HeapTop(Heap* hp);
HPDataType HeapTop(Heap* hp)
{
  assert(hp);
  assert(hp->_size > 0);
  return hp->_a[0];
}
// 堆的数据个数
int HeapSize(Heap* hp);
int HeapSize(Heap* hp)
{
  assert(hp);
  return hp->_size;
}
// 堆的判空
int HeapEmpty(Heap* hp);
int HeapEmpty(Heap* hp)
{
  assert(hp);
  return hp->_size == 0;
}
void Print(Heap* h1);
void Print(Heap* h1)
{
  for (int i=0;i<h1->_size;i++)
  {
    printf("%d ", h1->_a[i]);
  }
  printf("\n");
}
// TopK问题：找出N个数里面最大/最小的前K个问题。
// 比如：未央区排名前10的泡馍，西安交通大学王者荣耀排名前10的韩信，全国排名前10的李白。等等问题都是Topk问题，
// 需要注意：
// 找最大的前K个，建立K个数的小堆
// 找最小的前K个，建立K个数的大堆
//我这里是大根堆，所以我们第一个父节点永远是最大的
//可能左节点的孩子比右节点大，可能右节点的孩子比左节点大，但是他们都比自身的父节点小
//他们的父节点又比自身的父节点小，所以层层从下往上推，第一个父节点肯定是最大的
void PrintTopK(int* a, int n, int k, Heap* h1);
void PrintTopK(int* a, int n, int k, Heap* h1)
{
  assert(h1->_size >= k);
  while (k--)
  {
    printf("%d ", HeapTop(h1));
    HeapPop(h1);
  }
}
//void PrintTopK1(int* a, int n, int k, Heap* h1);
//void PrintTopK1(int* a, int n, int k, Heap* h1)
//{
//  assert(h1->_size >= k);
//  while (k--)
//  {
//    printf("%d ",HeapTop(h1));
//    HeapPop(h1);
//  }
//}
void Swap(int* S1, int* S2);
void Swap(int* S1, int* S2)
{
  int tmp = 0;
  tmp = *S1;
  *S1 = *S2;
  *S2 = tmp;
}
void HeapAscrSort(int* Sort, int n,int parents);
void HeapAscrSort(int* Sort, int n,int parents)
{
  int i = n;
  for (int i = (n-2)/2;i>=0;i--)
  {
    AdjustDown(Sort, n, i);
  }
  int End =n-1;
  while (End>0)
  {
    Swap(&Sort[0], &Sort[End]);
    AdjustDown(Sort, End, parents);
    End--;
  }
}

#define  _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include "big small Heap.h"
int main()
{
  //Heap H1;
  ///*HeapCreate(arr,7,6);*/
  HPDataType arr[12] = {0,0,70,50,35,90,100,111,1,121,1211,-200000};
  HeapAscrSort(arr, 12, 0);
  for (int i =0;i<12;i++)
  {
    printf("%d ", arr[i]);
  }
  //HeapCreate(&H1, arr, 9);
  //Print(&H1); 
  //HeapPop(&H1);
  //Print(&H1);
  //HeapPop(&H1);
  //Print(&H1);
  //HeapPop(&H1);
  //Print(&H1);
  //HeapPop(&H1);
  Print(&H1);
  //HeapPop(&H1);
  //HeapPop(&H1);
  //HeapPop(&H1);
  //HeapPop(&H1);
  //HeapPop(&H1);
  //HeapPop(&H1);
  //HeapPop(&H1);
  //HeapPop(&H1);
  //int b = HeapEmpty(&H1);
  //PrintTopK(arr,9,9,&H1);
}