堆的概念與結(jié)構(gòu)

概念：如果有一個(gè)關(guān)鍵碼的集合K={ k0，k1 ，k2 ，…，kn-1 },把它的所有元素按完全二叉樹的順序存儲方式存儲 在一個(gè)一維數(shù)組中，并滿足K i<=K 2*i+1且Ki<=K 2*i+2(K i>=K 2*i+1且Ki>=K 2*i+2) i = 0，1，2...，則稱為小堆(或大堆)。將根節(jié)點(diǎn)最大的堆叫做最大堆或大根堆，根節(jié)點(diǎn)最小的堆叫做最小堆或小根堆。

性質(zhì)：

• 堆中某個(gè)節(jié)點(diǎn)的值總是不大于或不小于其父節(jié)點(diǎn)的值；
• 堆總是一棵完全二叉樹。

結(jié)構(gòu)：

1.大堆

2.小堆

堆(大根堆)的實(shí)現(xiàn)：

堆的接口：

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int HPDataType;
typedef struct Heap
{
  HPDataType* a;
  int size;
  int capacity;
}HP;

//堆的創(chuàng)建
void HeapInit(HP*hp);
//堆的銷毀
void HeapDestroy(HP*hp);
//交換數(shù)值
void Swap(HPDataType *px, HPDataType *py);
//向上調(diào)整
void AdjustUp(int *a,int child);
//向下調(diào)整
void AdjustDown(int *a, int n, int parent);
//堆的插入
void HeapPush(HP*hp,HPDataType x);
//堆的刪除
void HeapPop(HP*hp);
//取堆頂?shù)臄?shù)據(jù)
HPDataType HeapTop(HP*hp);
//打印堆
void HeapPrint(HP*hp);
//堆的判空
bool HeapEmpty(HP*hp);
//堆的數(shù)據(jù)個(gè)數(shù)
int HeapSize(HP*hp);

堆的創(chuàng)建：

void HeapInit(HP*hp)
{
  assert(hp);
  hp->a=NULL;
  hp->capacity=hp->size=0;
}

堆的銷毀：

void HeapDestroy(HP*hp)
{
  assert(hp);
  free(hp->a);
  hp->capacity=hp->size=0;
}

交換數(shù)值：

void Swap(HPDataType*px, HPDataType*py)
{
  HPDataType tmp = *px;
  *px=*py;
  *py=tmp;
}

向上調(diào)整：

void AdjustUp(int*a, int child)
{
	assert(a);
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] > a[parent])
		{
          //交換數(shù)值
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

堆得插入：

void HeapPush(HP*hp,HPDataType x)
{
  assert(hp);
  if(hp->capacity==hp->size)
  {
      size_t newCapacity=hp->capacity==0?4:hp->capacity*2;
      HPDataType * tmp=(HPDataType*)realloc(hp->a,newCapacity*sizeof(HPDataType));
      if(tmp==NULL)
      {
          printf("realloc is fail\n");
      }
      hp->a=tmp;
      hp->capacity=newCapacity;
      
  }
  hp->a[hp->size-1]=x;
  hp->size++;
  //向上調(diào)整
  AdjusiUp(hp->a,hp->size-1);
}

向下調(diào)整：

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])
      {
          child++;
      }
      if(a[child]>a[parent])
      {
          Swap(&a[child],&a[parent]);
          parent=child;
          child=parent*2+1;
      }
      else
      {
          break;
      }
  }
}

堆的判空：

bool HeapEmpty(HP*hp)
{
  assert(hp);
  return hp->size==0;
}

堆的刪除：

void HeapPop(HP*hp)
{
	assert(hp);
  //堆的判空
	assert(!HeapEmpty(hp));
  //交換數(shù)值
	Swap(&hp->a[0], &hp->a[hp->size - 1]);
	hp->size--;
  //向下調(diào)整
	AdjustDown(hp->a, hp->size, 0);
}

取堆頂?shù)臄?shù)據(jù)：

HPDataType HeapTop(HP*hp)
{
  assert(hp);
  assert(!HeapEmpty(hp));
  return hp->a[0];
}

打印堆：

void HeapPrint(HP*hp)
{
  assert(hp);
  assert(!HeapEmpty(hp));
  for(int i=0; i<hp->size;i++)
  {
      printf("%d",hp->a[i]);
  }
  printf("\n");
}

堆的數(shù)據(jù)個(gè)數(shù)：

int HeapSize(HP*hp)
{
  assert(hp);
  return hp->size;
}

以上就是對堆的講解與操作實(shí)現(xiàn)。

感謝老鐵看到這里，如果文章對你有用的話請給我一個(gè)贊支持一下，感激不盡！

在下才疏學(xué)淺,一點(diǎn)淺薄之見，歡迎各位大佬指點(diǎn)。

以上就是C語言 深入解讀數(shù)據(jù)結(jié)構(gòu)之堆的實(shí)現(xiàn)的詳細(xì)內(nèi)容，更多關(guān)于C語言 數(shù)據(jù)結(jié)構(gòu)的資料請關(guān)注服務(wù)器之家其它相關(guān)文章！

原文鏈接：https://blog.csdn.net/apple_52909052/article/details/121187795