数据结构中的堆是什么意思_数据结构筛选法建立初始堆

数据结构中的堆是什么意思_数据结构筛选法建立初始堆堆排序是一种利用堆数据结构进行排序的算法

目录

一、堆

1.1 堆的概念

1.2 堆的结构性质 

1.3 堆的实现

1.3.1 向上调整

1.3.2 向下调整

1.3.3 创建堆:

1.3.4 插入元素:

1.3.5 删除元素:

1.3.6 堆排序:

1.4 堆的应用

1.4.1 Top K 问题


一、堆

        在C语言中,堆(Heap)是一种基于二叉树结构的数据结构。与内存中的堆不同,此处的堆是指堆数据结构。

1.1 堆的概念

    堆是一种特殊的二叉树,它满足两个性质

  1. 堆总是一棵完全二叉树:除了最后一层外,其他层的节点数都是满的,最后一层的节点都尽量靠左排列。
  2. 堆中每个节点的值都满足堆的性质:堆中某个节点的值总是不大于或不小于其父节点的值。最大堆又称大根堆(Max Heap),父节点的值大于等于其子节点的值;最小堆又称小根堆(Min Heap),父节点的值小于等于其子节点的值。

1.2 堆的结构性质 

        堆是一种基于二叉树结构的数据结构,一般使用数组来实现,因为对于完全二叉树来说,可以利用数组的索引来表示节点之间的关系。

通常,堆具有以下性质

  1. 根节点索引一般为0
  2. 对于堆中其余的任意节点i,它的左孩子节点为2i+1,右孩子节点为2i+2,父节点为(i-1)/2。
  3. 每个节点的左右子树也必须是一个堆
  4. 小堆不是升序,大堆不是降序

数据结构中的堆是什么意思_数据结构筛选法建立初始堆

1.3 堆的实现

1.3.1 向上调整

        向上调整通常在插入元素到堆中后使用,以确保新插入的元素满足堆的性质。

具体步骤如下

  1. 将新插入的元素放置在堆的最后一个位置(通常是数组的末尾)。
  2. 将该元素与其父节点进行比较。
  3. 若该元素大于(或小于,具体根据堆是最大堆还是最小堆而定)其父节点的值,则交换该元素和其父节点的位置。
  4. 继续向上对比和交换,直到满足堆的性质或达到堆的根节点。
void AdjustUp(HPDataType* arr, int child)
{
	assert(arr);
	int parent = (child - 1) / 2;
	while (child>0)
	{
		if (arr[child] < arr[parent])
		{
			swap(&arr[child], &arr[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

1.3.2 向下调整

        给出一个数组,逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆(或大堆)。向下调整算法有一个前提:左右子树必须是一个堆,才能调整。

 具体步骤如下:

  1. 从堆顶元素开始,将其与其子节点中较大(或较小)的节点进行比较。
  2. 若堆顶元素小于(或大于,具体根据堆是最大堆还是最小堆而定)其子节点的值,则将其与较大(或较小)的子节点进行交换,并继续向下比较和交换。
  3. 继续向下对比和交换,直到满足堆的性质或达到堆的末尾。
void AdjustDown(HPDataType* arr,int size, int parent)
{
	assert(arr);
	HPDataType child = parent * 2 + 1;
	
	while (child < size)
	{
		if (child + 1 < size && arr[child + 1] < arr[child])
		{
			child++;
		}
		if (arr[child] < arr[parent])
		{
			swap(&arr[parent], &arr[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}

}

1.3.3 创建堆:

 步骤如下:

  1. 创建一个空堆,可以使用一个数组来存储堆的节点,并初始化堆的大小为0。
  2. 一般使用自底向上的方式构建堆,从最后一个非叶子节点开始,依次向上进行堆调整操作。(也可以使用依次插入元素建堆)
//小堆
typedef int HPDataType;
typedef struct {
	HPDataType* a;
	int size;
	int capacity;
}hp;

//初始化堆
void HpInit(hp* php)
{
	assert(php);
	php->a = NULL;
	php->capacity = 0;
	php->size = 0;
}

//创建堆
void HPCrearK(HPDataType* arr, int len)
{
    assert(arr);
	int parent = ((len - 1) - 1) / 2;
	while (parent >= 0)
	{
		AdjustDown(arr, len, parent);
		parent--;
	}
}

1.3.4 插入元素:

基本思想:

        将一个新的元素插入到堆中,保持堆的性质。

步骤如下:

  1. 将新的元素插入到堆的末尾
  2. 依次与父节点比较,进行交换操作(向上调整),
  3. 重复2,直到满足堆的性质。
//插入元素
void HpPush(hp* php, HPDataType x)
{
	assert(php);
	if (php->size == php->capacity)
	{
		int NewCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(php->a,sizeof(HPDataType) * NewCapacity);
		if (tmp == NULL)
		{
			perror("malloc error!");
			return;
		}
		php->a = tmp;
	}
	php->a[php->size] = x;
	php->size++;
	AdjustUp(php->a, php->size-1);

}

1.3.5 删除元素:

        删除元素时,通常删除堆顶元素。将堆顶元素与数组末尾的元素交换,然后删除末尾元素,并调整堆的结构,确保堆继续满足堆的性质。

//判空
bool HpEmpty(hp* php)
{
	assert(php);
	return php->size == 0;
}

//交换元素
void swap(HPDataType* a1, HPDataType* a2)
{
	HPDataType tmp = *a1;
	*a1 = *a2;
	*a2 = tmp;
}

//删除堆顶元素
void HpPop(hp* php)
{
	assert(php);
	assert(!HpEmpty(php));
	swap(&php->a[0] , &php->a[php->size - 1]);
	php->size--;
	AdjustDown(php->a, php->size, 0);
}

1.3.6 堆排序:

        利用堆进行排序的方法称为堆排序。

具体步骤:

  1. 将待排序的数组构建成一个堆(向下调整)
  2. 从后向前依次堆顶元素放入数组中,并删除堆顶元素
  3. 重复2,直至最终得到排序好的数组。
//堆排序
void HpSort(HPDataType* arr, int len)
{
	assert(arr);
	int parent = ((len - 1) - 1) / 2;
	while (parent >= 0)
	{
		AdjustDown(arr, len, parent);
		parent--;
	}

	int end = len - 1;
	while (end > 0)
	{
		swap(&arr[0], &arr[end]);

		// 再调整,选出次小的数
		AdjustDown(arr, end, 0);

		end--;
	}
}

1.4 堆的应用

1.4.1 Top K 问题

TOP-K问题:即求数据结合中前K个最大的元素或者最小的元素,一般情况下数据量都比较大。

具体步骤如下:

  1. 用数据集合中前K个元素来建堆
    前k个最大的元素,建小堆
    前k个最小的元素,则建大堆
  2. 用剩余的N-K个元素依次与堆顶元素来比较,不满足则替换堆顶元素

将剩余N-K个元素依次与堆顶元素比完之后,堆中剩余的K个元素就是所求的前K个最小或者最大的元素。

//创建大小为K的堆
hp* HPCrearK(int k)
{
	hp* tmp = (hp*)malloc(sizeof(hp));
	if (tmp == NULL)
	{
		perror("malloc error!");
		return NULL;
	}
	HpInit(tmp);
	HPDataType* arr = (HPDataType*)malloc(sizeof(HPDataType) * k);
	if (arr == NULL)
	{
		perror("malloc error!");
		return NULL;
	}
	tmp->a = arr;
	tmp->capacity = k;
	return tmp;
}

//Topk
HPDataType TopK(HPDataType* arr, int k, int len)
{
	assert(arr);
	if (k > len)
	{
		return EOF;
	}
	hp* php = HPCrearK(k);
	if (php == NULL)
	{
		perror("Creat error");
		return EOF;
	}
	for (int i = 0; i < k; i++)
	{
		HpPush(php, arr[i]);
	}
	for (int i = k; i < len; i++)
	{
		if (arr[i] > HpTop(php))
		{
			HpPop(php);
			HpPush(php, arr[i]);
		}
	}
	return HpTop(php);
}

今天的文章数据结构中的堆是什么意思_数据结构筛选法建立初始堆分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/81935.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注