數據結構之堆的具體使用

Posted on by

堆的概念及結構

在這裡插入圖片描述

在這裡插入圖片描述

定義堆

實現堆的功能首先要定義堆的結構體

typedef int HPDataTpye;

typedef struct Heap
{
	HPDataTpye* a;		//存儲數據
	int size;           //保存元素個數
	int capacity;       //存儲容量
}HP;

堆的初始化

思路：

  • 先開辟一塊空間，將傳入的數據存放到堆的結構體中
  • 將堆中數據建堆排序
  • 將堆結構中容量，元素個數初始化

開辟空間不難，那麼如何建堆呢？

這裡有兩種思路，一是從上往下調整，二是從下往上調整

思路一：
從上往下調整

將傳入的結點當做父節點，比較其兩個子節點，將子節點與父節點比較，如果不滿足堆的條件就交換，並將原先子節點的位置當成父節點，重復上述操作。如果滿足堆的條件就結束操作。（註意：該程序是建立在左右子樹都為大堆基礎上的）

在這裡插入圖片描述

代碼如下

void Swap(int* px, int* py)
{
	int tmp = *px;
	*px = *py;
	*py = tmp;
}
// 條件：左右子樹都是小堆/大堆
void AdjustDown(int* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		// 選出左右孩子中小 or 大的那個
		if (child + 1 < n && a[child + 1] < a[child])
		{
			++child;
		}

		// 1、如果小 or 大的孩子比父親小 or 大，則交換，繼續往下調整
		// 2、如果小 or 大 的孩子比父親大 or 小，則結束調整
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

思路二：
從下往上建

將傳入的結點當做子節點，找到其父結點並與之比較，不滿足堆的條件就交換，並將原父結點的位置當成子節點重復之前操作。滿足堆的條件則退出程序。（註意：該程序建立在除傳入的子節點外，其餘結點都滿足堆條件基礎上的）

在這裡插入圖片描述

代碼實現

void Swap(int* px, int* py)
{
	int tmp = *px;
	*px = *py;
	*py = tmp;
}
void AdjustUp(int* a, int child)
{
	int parent = (child - 1) / 2;
	//while (parent >= 0)  不對的 parent不會小於0
	while (child > 0)
	{
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

初始化總體代碼

void Swap(int* px, int* py)
{
	int tmp = *px;
	*px = *py;
	*py = tmp;
}

// 條件：左右子樹都是小堆/大堆
void AdjustDown(int* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		// 選出左右孩子中小 or 大的那個
		if (child + 1 < n && a[child + 1] < a[child])
		{
			++child;
		}

		// 1、如果小 or 大的孩子比父親小 or 大，則交換，繼續往下調整
		// 2、如果小 or 大 的孩子比父親大 or 小，則結束調整
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void AdjustUp(int* a, int child)
{
	int parent = (child - 1) / 2;
	//while (parent >= 0)  不對的 parent不會小於0
	while (child > 0)
	{
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

void HeapInit(HP* php, HPDataTpye* a, int n)
{
	assert(php);
	//開辟空間
	php->a = (HPDataTpye*)malloc(sizeof(HPDataTpye)*n);
	if (php->a == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	//轉移數據
	memcpy(php->a, a, sizeof(HPDataTpye)*n);
	//建堆排序
	for (int i = (n - 2) / 2; i >= 0; i--)
	{
		AdjustDown(php->a, n, i);
	}

	php->capacity = n;
	php->size = n;
}

插入數據

思路：

  • 檢查是否滿容量，滿瞭就擴容
  • 插入數據，並將size+1

代碼：

void HeapPush(HP* php, HPDataTpye x)
{
	assert(php);
	if (php->capacity == php->size)
	{
		HPDataTpye* tmp = (HPDataTpye*)realloc(php->a, 2 * php->capacity*sizeof(HPDataTpye));
		if (php->a == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		php->capacity *= 2;
	}
	php->a[php->size] = x;
	php->size++;

	AdjustUp(php->a, php->size - 1);
}

判空

思路：

判空隻需判斷其元素個數是否為0即可

代碼：

bool HeapEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}

刪除堆頂的數據

思路：

  • 先判空處理
  • 將堆頂數據和最後一個葉結點數據交換
  • 從上往下調整堆

在這裡插入圖片描述

代碼：

void HeapPop(HP* php)
{
	assert(php);
	assert(!HeapEmpty(php));
	//交換頭尾數據
	Swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;

	AdjustDown(php->a, php->size, 0);
}

獲取堆頂數據

思路：

先判空，再取出堆頂數據

代碼：

HPDataTpye HeapTop(HP* php)
{
	assert(php);
	assert(!HeapEmpty(php));

	return php->a[0];
}

獲取元素個數

直接返回size

int HeapSize(HP* php)
{
	assert(php);
	return php->size;
}

打印

void HeapPrint(HP* php)
{
	for (int i = 0; i < php->size; i++)
	{
		printf("%d ", php->a[i]);
	}
	printf("\n");
}

銷毀堆

將開辟的空間釋放，並將size,capacity賦值為0

void HeapDestroy(HP* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->capacity = php->size = 0;
}

Topk問題

問：如何取出一組數據中最大的前K個值

有人會想到把所有數據建大堆，取出堆頂數據再刪除該數據，重復操作K次
操作如下

void TestHeap()
{
	int a[] = { 27, 37, 28, 18, 19, 34, 65, 4, 25, 49, 15 };
	HP hp;
	HeapInit(&hp, a, sizeof(a) / sizeof(int));
	HeapPrint(&hp);

	printf("\n");

	int k = 0;
	scanf("%d", &k);
	printf("找出數組中最小的前%d個：", k);
	while (!HeapEmpty(&hp)&&k--)
	{
		printf("%d ", HeapTop(&hp));
		HeapPop(&hp);
	}
	printf("\n");
}

在這裡插入圖片描述

如果該組數據個數為一萬，十萬呢？

這時用該方法不但耗費時間而且十分耗內存，那有沒有時間復雜符度較小的用堆實現的方法呢？
答案是有的，那就是Topk算法

Topk基本思路如下：

用數據集合中前K個元素來建堆
求前k個最大的元素，則建小堆
求前k個最小的元素，則建大堆用剩餘的N-K個元素依次與堆頂元素來比較，不滿足則替換堆頂元素
將剩餘N-K個元素依次與堆頂元素比完之後，堆中剩餘的K個元素就是所求的前K個最小或者最大的元素。

代碼實現

void PrintTopK(int* a, int n, int k)
{
	HP hp;
	HeapInit(&hp, a, k);

	for(int i = k; i < n; i++)
	{
		if (a[i]>HeapTop(&hp))
		{
			HeapPop(&hp);
			HeapPush(&hp, a[i]);
		}
	}
	HeapPrint(&hp);
	HeapDestroy(&hp);
}

檢測

這裡利用隨機數來檢測

void TestTopk()
{
	int n = 100000;
	int* a = (int*)malloc(sizeof(int)*n);
	srand(time(0));
	for (size_t i = 0; i < n; ++i)
	{
		a[i] = rand() % 1000000;
	}
	a[5] = 1000000 + 1;
	a[1231] = 1000000 + 2;
	a[531] = 1000000 + 3;
	a[5121] = 1000000 + 4;
	a[115] = 1000000 + 5;
	a[2335] = 1000000 + 6;
	a[9999] = 1000000 + 7;
	a[76] = 1000000 + 8;
	a[423] = 1000000 + 9;
	a[3144] = 1000000 + 10;

	PrintTopK(a, n, 10);
}

運行結果

在這裡插入圖片描述

代碼總結

Heap.h 頭文件

#define _CRT_SECURE_NO_WARNINGS 1
#pragma once

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include<time.h>

typedef int HPDataTpye;

typedef struct Heap
{
	HPDataTpye* a;
	int size;
	int capacity;
}HP;

void Swap(int* px, int* py);
void AdjustDown(int* a, int n, int parent);
void AdjustUp(int* a, int child);


//void HeapInit(HP* php);
//初始化
void HeapInit(HP* php, HPDataTpye* a, int n);
// 插入x，保持他繼續是堆
void HeapPush(HP* php, HPDataTpye x);
//判空
bool HeapEmpty(HP* php);
// 刪除堆頂數據，刪除後保持他繼續是堆
void HeapPop(HP* php);
// 獲取堆頂的數據，也就是最值
HPDataTpye HeapTop(HP* php);
//獲取堆中元素個數
int HeapSize(HP* php);
//打印
void HeapPrint(HP* php);
//銷毀堆
void HeapDestroy(HP* php);

Heap.c 函數文件

#define _CRT_SECURE_NO_WARNINGS 1
#include "Heap.h"

void Swap(int* px, int* py)
{
	int tmp = *px;
	*px = *py;
	*py = tmp;
}

// 條件：左右子樹都是小堆/大堆
void AdjustDown(int* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		// 選出左右孩子中小 or 大的那個
		if (child + 1 < n && a[child + 1] < a[child])
		{
			++child;
		}

		// 1、如果小 or 大的孩子比父親小 or 大，則交換，繼續往下調整
		// 2、如果小 or 大 的孩子比父親大 or 小，則結束調整
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void AdjustUp(int* a, int child)
{
	int parent = (child - 1) / 2;
	//while (parent >= 0)  不對的 parent不會小於0
	while (child > 0)
	{
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

void HeapInit(HP* php, HPDataTpye* a, int n)
{
	assert(php);
	//開辟空間
	php->a = (HPDataTpye*)malloc(sizeof(HPDataTpye)*n);
	if (php->a == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	//轉移數據
	memcpy(php->a, a, sizeof(HPDataTpye)*n);
	//建堆排序
	for (int i = (n - 2) / 2; i >= 0; i--)
	{
		AdjustDown(php->a, n, i);
	}

	php->capacity = n;
	php->size = n;
}

// 插入x，保持它繼續是堆
void HeapPush(HP* php, HPDataTpye x)
{
	assert(php);
	if (php->capacity == php->size)
	{
		HPDataTpye* tmp = (HPDataTpye*)realloc(php->a, 2 * php->capacity*sizeof(HPDataTpye));
		if (php->a == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		php->capacity *= 2;
	}
	php->a[php->size] = x;
	php->size++;

	AdjustUp(php->a, php->size - 1);
}

bool HeapEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}

// 刪除堆頂數據，刪除後保持他繼續是堆
void HeapPop(HP* php)
{
	assert(php);
	assert(!HeapEmpty(php));

	Swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;

	AdjustDown(php->a, php->size, 0);
}

// 獲取堆頂的數據，也就是最值
HPDataTpye HeapTop(HP* php)
{
	assert(php);
	assert(!HeapEmpty(php));

	return php->a[0];
}


int HeapSize(HP* php)
{
	assert(php);
	return php->size;
}

void HeapPrint(HP* php)
{
	for (int i = 0; i < php->size; i++)
	{
		printf("%d ", php->a[i]);
	}
	printf("\n");
}

void HeapDestroy(HP* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->capacity = php->size = 0;
}

test.c 測試文件

#include "Heap.h"

void TestHeap()
{
	int a[] = { 27, 37, 28, 18, 19, 34, 65, 4, 25, 49, 15 };
	HP hp;
	HeapInit(&hp, a, sizeof(a) / sizeof(int));
	HeapPrint(&hp);

	printf("\n");

	int k = 0;
	scanf("%d", &k);
	printf("找出數組中最小的前%d個：", k);
	while (!HeapEmpty(&hp)&&k--)
	{
		printf("%d ", HeapTop(&hp));
		HeapPop(&hp);
	}
	printf("\n");
}

void PrintTopK(int* a, int n, int k)
{
	HP hp;
	HeapInit(&hp, a, k);

	for(int i = k; i < n; i++)
	{
		if (a[i]>HeapTop(&hp))
		{
			HeapPop(&hp);
			HeapPush(&hp, a[i]);
		}
	}
	HeapPrint(&hp);
	HeapDestroy(&hp);
}

void TestTopk()
{
	int n = 100000;
	int* a = (int*)malloc(sizeof(int)*n);
	srand(time(0));
	for (size_t i = 0; i < n; ++i)
	{
		a[i] = rand() % 1000000;
	}
	a[5] = 1000000 + 1;
	a[1231] = 1000000 + 2;
	a[531] = 1000000 + 3;
	a[5121] = 1000000 + 4;
	a[115] = 1000000 + 5;
	a[2335] = 1000000 + 6;
	a[9999] = 1000000 + 7;
	a[76] = 1000000 + 8;
	a[423] = 1000000 + 9;
	a[3144] = 1000000 + 10;

	PrintTopK(a, n, 10);
}

int main()
{
	//TestHeap();
	TestTopk();

	return 0;
}

到此這篇關於數據結構之堆的具體使用的文章就介紹到這瞭,更多相關數據結構 堆內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：