堆的介绍~_ 字节宝

堆的逻辑结构是一棵完全二叉树堆的物理结构是一个数组

通过下标父子节点关系：leftchild=parent*2 1

rightchild=parent*2 2 parent=(child-1)/2

堆的两个特性

结构性

用数组表示的完全二叉树

有序性

任一节点的关键字是其他子树所有节点的最大值（或最小值）

最大堆：也称为大顶堆，最大值，所有父亲均大于孩子

最小堆：也称为小顶堆，最小值，所有父亲均小于孩子

代码语言：javascript复制

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int HPDataType;
typedef struct Heap
{
  HPDataType* a;
  int size;
  int capacity;
}HP;
void HPInit(HP* php);
void HPDestory(HP* php);
void HPPush(HP* php,HPDataType x);
void HPPop(HP* php);

初始化

代码语言：javascript复制

void HPInit(HP* php)
{
  assert(php);
  php->a=NULL;
  php->capcacity=php->size=0;
}

销毁

代码语言：javascript复制

void HPDestory(HP* php)
{
  assert(php);
  free(php->a);
  php->a=NULL;
  php->capcacity=php->size=0;
}

交换

代码语言：javascript复制

void Swap(HPDataType* p1,HPDataType* p2)
{
  HPDataType tmp=*p1;
  *p1=*p2;
  *p2=tmp;
}

向上调整

代码语言：javascript复制

void AdjustUp(HPDataType* a,int child)//建立小堆
{
   int parent=(child-1)/2;
   while(child>0) 实际上，结束条件是当child变为0（即到达根节点）或者当前节点不小于其父节点时
   {
      if(a[parent]>a[child]}
      {
         Swap(a[parent]>a[child]);
      child=parent;//parent当上了child，继续向上调整
      parent=(child-1)/2;
      }
      else
        break;
   }
}

插入元素

代码语言：javascript复制

void HPPush(HP* php,HPDataType x)
{
   assert(php);

	if (php->size == php->capacity)
	{
		int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(php->a, newcapacity * sizeof(HPDataType));
		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);//传的是数组最后一个元素的下标 如果传size就越界了
}

向下调整

代码语言：javascript复制

void AdjustDown(HPDataType* a,int n,int parent)//参数 n 表示堆中当前有效元素的数量
{
   int child=parent*2 1;//先假设左孩子小，并计算左孩子的索引
   while(child<n)
//如果child大于n，说明孩子已经调整到n，调整到叶子结点了
// 如果子节点索引大于等于堆的大小，说明已经到达了叶子节点，无需继续调整
   {
      if(child 1<n&&a[child]<a[child 1])//首先要保证存在右孩子节点 
      {
            child;
      }
      if (a[child] < a[parent])
	  {
			Swap(&a[child], &a[parent]);
			parent = child;//更新child为parent
			child = parent * 2   1;
      }
      else
         break;
    }
}

删除数据

代码语言：javascript复制

void HPpop(HP* php)
{
   assert(php);
   assert(php->size>0);
   Swap(&php->a[0], &php->a[php->size-1]);
   php->size--;
   AdjustDown(php->a, php->size, 0);
}

取栈顶数据

代码语言：javascript复制

HPDataType HPTop(HP* php)
{
	assert(php);
	assert(php->size > 0);

	return php->a[0];
}

判空

代码语言：javascript复制

bool HPEmpty(HP*php)
{
  assert(php);
  return php->size==0;
}

test.c

方法一

代码语言：javascript复制

void TestHeap1()
{
  int a[] = { 4,2,8,1,5,6,9,7,3,2,23,55,232,66,222,33,7,1,66,3333,999 };
  Hp hp;
  HPInit(&hp);
  for(size_t i=0;i<sizeof(a)/sizeof(int);i  )
  {
     HPPush(&hp,a[i]);
  }
  while(!HPEmpty(&hp))
  {
     printf("%d",HPTop(&hp);
  }
  HPDestory(&hp)；
}

方法二

首先说明最后一个非叶子结点的坐标为什么是(n-1-1)/2?

堆的最后一个元素的索引是n-1（因为数组是从0开始索引的）。
在完全二叉树中，如果一个节点的索引是i，那么它的左子节点的索引是2*i 1，右子节点的索引是2*i 2
那么根据最后一个元素的索引是n-1，这个最后一个元素可以是左子节点，那么i=(n-1-1)/2,如果这个最后一个元素为右子节点，那么

代码语言：javascript复制

void HeapSort(int* a,int n)
{
   for(int i=(n-1-1)/2;i>0;i--)
   {
      AdjustDown(a, n, i);// 向下调整建堆 O(N)
   }
   
   // O(N*logN)
   int end=n-1;
   while(end>0)
   {
      Swap(&a[0], &a[end]);
	  AdjustDown(a, end, 0);
	  --end;
	}
}
      
   
  
void TestHeap2()
{
	int a[] = { 4,2,8,1,5,6,9,7,2,7,9};
	HeapSort(a, sizeof(a) / sizeof(int));
}

代码语言：javascript复制

void CreatDate()
{  
   int n=100000;
   srand(time(0));
   const char* file="data.txt";
   //fopen函数的返回值被存储在FILE类型的指针fin中 
   FILE* fin=fopen(file,"w");
   if (fin == NULL)
   {
		perror("fopen error");
		return;
	}
   for(int i=0;i<n;i  )
   {
     int x = (rand() i) % 10000000; 
     fprintf(fin,"%d",x);
   }
   fclose(fin);
}

实现了一个基于堆（Heap）的数据结构来找出并输出给定文件data.txt中最大的前k个数

代码语言：javascript复制

void TestHeap()
{
  int k;
  printf("请输入k：");
  scanf("%d",&k);
  int* kminheap=(int*)malloc(sizeof(int)*k);
  if(kminheap==NULL)
  {  
     perror("malloc fail");
     return NULL;
  }
  const char*file="data.txt";
  FILE* fout=fopen(file,"r");
  if (fout == NULL)  
  {  
    perror("fopen 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 x=0;
  while(fscanf(fout,%d,&x)>0)
  {
     if(kminheap[0]<x)
     {
        kminheap[0] = x;  
        AdjustDown(kminheap, k, 0);  
     } 
   }
   printf("最大前%d个数：", k);  
   for (int i = 0; i < k; i  )  
   {  
      printf("%d ", kminheap[i]);  
   }  
   printf("n");
 }