欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数据结构之堆的基本操作

程序员文章站 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];
    }
}

运行结果

数据结构之堆的基本操作