C语言 深入解读数据结构之堆的实现

堆的概念与结构

概念：如果有一个关键码的集合k={ k0，k1 ，k2 ，…，kn-1 },把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中，并满足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...，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

性质：

• 堆中某个节点的值总是不大于或不小于其父节点的值；
• 堆总是一棵完全二叉树。

结构：

1.大堆

2.小堆

堆(大根堆)的实现：

堆的接口：

#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;
 
//堆的创建
void heapinit(hp*hp);
//堆的销毁
void heapdestroy(hp*hp);
//交换数值
void swap(hpdatatype *px, hpdatatype *py);
//向上调整
void adjustup(int *a,int child);
//向下调整
void adjustdown(int *a, int n, int parent);
//堆的插入
void heappush(hp*hp,hpdatatype x);
//堆的删除
void heappop(hp*hp);
//取堆顶的数据
hpdatatype heaptop(hp*hp);
//打印堆
void heapprint(hp*hp);
//堆的判空
bool heapempty(hp*hp);
//堆的数据个数
int heapsize(hp*hp);

堆的创建：

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;
}

交换数值：

void swap(hpdatatype*px, hpdatatype*py)
{
    hpdatatype tmp = *px;
    *px=*py;
    *py=tmp;
}

向上调整：

void adjustup(int*a, int child)
{
	assert(a);
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] > a[parent])
		{
            //交换数值
			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++;
    //向上调整
    adjusiup(hp->a,hp->size-1);
}

向下调整：

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));
    //交换数值
	swap(&hp->a[0], &hp->a[hp->size - 1]);
	hp->size--;
    //向下调整
	adjustdown(hp->a, hp->size, 0);
}

取堆顶的数据：

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");
}

堆的数据个数：

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

以上就是对堆的讲解与操作实现。

感谢老铁看到这里，如果文章对你有用的话请给我一个赞支持一下，感激不尽！

在下才疏学浅,一点浅薄之见，欢迎各位大佬指点。

以上就是c语言 深入解读数据结构之堆的实现的详细内容，更多关于c语言 数据结构的资料请关注其它相关文章！