数据结构之堆的基本操作
程序员文章站
2024-02-15 08:03:28
...
今天我们来说一说堆,堆是一个完全二叉树,堆分大堆和小堆。
小堆: 这个树的根节点是这个树中的最小元素
对于任意一个子树来说, 子树的根节点, 小于左右孩子节点的值.
大堆: 这个树的根节点是这个树的最大元素
对于任意一个子树来说, 子树的根节点, 大于左右孩子节点的值.
下面我们画图来说明一下。
下面我们实现堆的基本操作
1、定义一个堆
我们定义一个堆的结构体,将堆的层序遍历结果储存在这个数组中,所以结构体内我们定义一个数组,数组长度,一个函数指针(这个函数指针定义判断是大堆还是大堆的函数)。
typedef struct Heap
{
HeapType data[HEAPSIZE];
size_t size;
Compare cmp;
}Heap;
2、堆的初始化
void HeapInit(Heap* heap,Compare cmp)
{
if(heap == NULL)
{
return;
}
heap->cmp = cmp;
heap->size = 0;
}
3、堆的销毁
当这个函数指针为空,size=0(即为无效元素)时,这个堆就被销毁了。
void HeapDestory(Heap* heap)
{
if(heap == NULL)
{
return;
}
heap->cmp = NULL;
heap->size = 0;
}
4、向堆中插入一个元素
首先我们先向这个数组进行尾插,因为尾插后依旧要满足一个堆的结构,所以再进行一个上浮式调整。
void Swap(HeapType* a,HeapType* b)
{
HeapType tmp = *a;
*a = *b;
*b = tmp;
}
void HeapInsert(Heap* heap,HeapType to_insert)
{
if(heap == NULL)
{
return;
}
if(heap->size >= HEAPSIZE)
{
return;
}
heap->data[heap->size++] = to_insert; //进行尾插
size_t child = heap->size-1; //定义数组中最后一个元素坐标为child
size_t parent = (child-1)/2; //利用公式算出child的parent是数组中的哪个坐标
while(child > 0)
{
if(heap->cmp(heap->data[child],heap->data[parent]))
{
//当data[child],data[parent]满足函数指针定义的大堆函数时(即data[child]>data[parent]),交换他们的位置
Swap(&heap->data[child],&heap->data[parent]);
child = parent; //将child坐标更新为原来parent坐标,进行下一次的上浮
parent = (child-1)/2;
}
else
{
break;
}
}
return;
}
5、堆的创建
根据一个数组创建一个堆,就是将数组中的元素循环的插入堆中,每一次的插入HeapInsert函数都会调整堆的结构。
void HeapCreate(Heap* heap,HeapType array[],size_t size)
{
if(heap == NULL || array == NULL || size == 0)
{
return;
}
{
size_t i ;
for(i=0;i<size;i++)
{
HeapInsert(heap,array[i]);
}
}
}
6、取堆顶元素
堆顶元素就是我们的坐标为0的元素,取出来,返回1。
int HeapRoot(Heap* heap,HeapType* root)
{
if(heap == NULL)
{
return;
}
if(heap->size == 0)
{
return;
}
*root = heap->data[0];
return 1;
}
7、删除堆顶元素
首先我们将堆顶元素与最后一个元素进行交换,此时堆顶元素已经是最后一个元素了,再进行尾删。因为尾删后我们依旧要保持一个堆的结构,所以要进行下沉式调整。
void HeapErase(Heap* heap)
{
if(heap == NULL)
{
return;
}
if(heap->size == 0)
{
return;
}
Swap(&heap->data[0],&heap->data[heap->size-1]);//将堆顶元素和最后一个元素交换
--heap->size; //进行尾删
size_t parent = 0;
size_t child = parent*2+1;
while(child >= 0 && child < heap->size && parent >= 0 && parent < heap->size)
{
if(child+1 < heap->size)
{
if(!heap->cmp(heap->data[child],heap->data[child+1]))
{
child = child+1;
}
}
if(heap->data[child] > heap->data[parent])
{
//当data[child]>data[parent],进行交换
Swap(&heap->data[child],&heap->data[parent]);
parent = child; //更新坐标
child = parent*2+1;
}
else
{
break;
}
}
}
8、堆的排序
删除堆顶元素的时候,每删除一个元素之后进行了下沉式调整,数组都将变得有序。
所以在堆的排序中,我们先根据已给定要排序数组创建一个堆,在循环对这个堆进行删除。
最后将保存堆的数组拷贝至原数组中。
void HeapSort(Heap *heap,HeapType array[],size_t size)
{
if(array == NULL || size == 0)
{
return;
}
HeapCreate(heap,array,size);
size_t i = 0;
for(;i<size;i++)
{
HeapErase(heap);
}
heap->size = size;
for(i=0;i<size;i++)
{
array[i] = heap->data[i];
}
}
运行结果