I 用c I 实现 大顶堆

一、堆的实现

1.堆结构：

     逻辑结构上类似于 一棵 “树”

 

 

2.堆的种类：

   大顶堆结构： 一种特殊的树：其每个子节点均比母节点要小

   小顶堆结构： 同理：其每个子节点均比母节点要大

结构图示：

2.大顶堆代码实现：（这里实现堆 用循序表的方式）

   ①初始化：

typedef int Heaptype;

typedef struct Heap
{
	Heaptype* head;   
	int size;         //记录堆总容量 
	int capacity;     //记录当前数据总个数
}Heap;

//堆的初始化
void Heap_Init(Heap* pphead)
{
	assert(pphead);
	pphead->head = NULL;
	pphead->size = 0;
	pphead->capacity = 0;
}

②插入数据：

 实现细节：数据在插入的同时，要进行数据结构的调整，使树顶始终保持最大数

                  如果新插入节点比母节点大的话，要进行交换 ，因此将这个调整结构的环节独立出来

                  即：“向上调整”。

 向上调整：因为插入数据时：新数据默认储存在顺序表尾，因此其逻辑上是在堆的底部，

                 所以，当新数据比母节点大时，它将与逻辑上处于其上方的母节点交换，称为

                 向上调整。

注：向上调整有时不止调整一次 ，还有可能调整多次，直到每个节点都在其相应位置 。

 流程图解：

大顶堆插入流程

细节点：因为数据是以顺序表的方式储存，所以子节点的下标与母节点的下标符合

              公式：parent = (child - 1)/2 ；(按照此公式带入计算就理解了) 

//向上调整
void adjust_up(Heap* pphead)
{
	int child = pphead->capacity;
	int parent = (child - 1) / 2;
	for (; pphead->head[parent] < pphead->head[child];)//判断是否符合大顶堆
	{
		swap(&(pphead->head[parent]),&(pphead->head[child]));//进行交换
		child = parent;
		parent = (child - 1) / 2;
	}
}

//插入数据
void Heap_push(Heap* pphead, Heaptype data)
{
	assert(pphead);
    //判断是否满容量并扩容
	Heap_realloc(pphead);
	pphead->head[pphead->capacity] = data;
    //向上调整
	adjust_up(pphead);
	pphead->capacity++;
}

③删除数据：为了避免因为直接删除头部数据导致整个堆的结构打乱，

这里先将头部数据与尾数据交换，然后将尾部数据删除，接着使用“向下调整”，即：将换上来的顶部数据向下与其子节点比较调整，直至符合大顶堆结构为止。

   注：1.大顶堆向下调整时，母节点要与两个子节点中较大的一个交换 ，因此要比较一下。

          2.这里下标的计算公式为：左孩子：child = (parent * 2) + 1

                                                 右孩子：child = (parent * 2) + 2

          3.计算孩子下标时要避免越界，避免将母节点与不属于堆中的数据比较。

//删除数据
void Heap_pop(Heap* pphead)
{
	assert(pphead);
	assert(pphead->capacity > 0);      //防止堆为空
    //将顶部数据与尾部数据交换
	swap(&(pphead->head[0]),&( pphead->head[pphead->capacity-1]));
	pphead->capacity--;
    //向下调整
	adjust_down(pphead,0);
}

//向下调整
void Adjust_down(int* a, int size, int parent)
{
	assert(a);
	for (int child = parent * 2 + 1; child <= size; child = parent * 2 + 1)
	{
        //默认用左孩纸与母节点比较，如果右孩纸比左孩纸大且不越界则交换
		if (a[child] > a[child + 1] && child + 1 <= size)
			child = child + 1;
        //比较孩纸和母节点
		if (a[child] < a[parent])
		{
			int temp = a[child];
			a[child] = a[parent];
			a[parent] = temp;
		}
        //向下继续比较
		parent = child;
	}
}

④扩容 || 判空 || 取顶数据 || 销毁堆

//判断是否扩容
void Heap_realloc(Heap* pphead)
{
	assert(pphead);
	if (pphead->size == pphead->capacity)
	{
		Heaptype Newsize = (pphead->size == 0) ? 4 : (pphead->size * 2);
		Heaptype* Newhead = (Heaptype*)realloc(pphead->head,sizeof(Heaptype) * Newsize);
		if (Newhead == NULL)
		{
			perror("realloc");
			exit(-1);
		}
		pphead->head = Newhead;
		pphead->size = Newsize;
	}
}

//判断堆是否为空
bool Heap_Empty(Heap* pphead)
{
	if (pphead->capacity)
		return false;
	return true;
}
//取对顶数据
Heaptype Heap_top(Heap* pphead)
{
	return pphead->head[0];
}
//销毁堆
void Heap_Destory(Heap* pphead)
{
	assert(pphead);
	free(pphead->head);
	pphead->head = NULL;
	pphead->size = 0;
	pphead->capacity = 0;
}

感谢访问！！！