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

数据结构-堆

程序员文章站 2024-02-14 09:45:28
...

堆的性质:

堆是按照完全二叉树的顺序存储方式存储在一个一维数组中。

堆分为小堆和大堆,不满足小堆和大堆性质的二叉树不能叫堆。

小堆:父节点的value < 任何一个子节点的value。(Ki <= K2 * i + 1)且(Ki <= K2 * i + 2);

大堆:父节点的value > 任何一个子节点的value。(Ki >= K2 * i + 1)且(Ki >= K2 * i + 2);

堆的操作:

  1. 初始化堆
  2. 创建堆
  3. 向堆中插入元素
  4. 打印堆的元素
  5. 获取堆顶元素
  6. 删除堆顶元素
  7. 判断是不是空堆
  8. 交换两个元素
  9. 小项堆的向下调整
  10. 堆排序
  11. 数据查找(从很多个数里面查找最大或者最小的K个数)


堆数据结构的定义(其实就是顺序表):

#define INIT_HEAP_SIZE 20
typedef int HeapDataType;
typedef struct Heap {
	HeapDataType* array;
	unsigned int capacity;
	unsigned int size;
}Heap;

Compare函数指针定义:

typedef int(*Compare)(int x, int y);

初始化堆

用于给堆中的元素开辟内存,以及初始化开辟内存

void initHeap(Heap* heap) {
	if (heap == NULL)
		return;
	heap->array = (HeapDataType*)malloc(sizeof(HeapDataType)*INIT_HEAP_SIZE);
	heap->capacity = INIT_HEAP_SIZE;
	heap->size = 0;
	for (int i = 0; i < heap->capacity; i++) {
		heap->array[i] = 0;
	}
}

创建堆

步骤:

  • 找到临界点
  • 从临界点开始向下调整(
  1. 找最小的左右孩子,
  2. 如果当前节点比最小孩子大,
  3. 则交换当前节点和最小孩子,
  4. 循环这个步骤,直到不满足条件

    )

  •     临界点自减1;继续以上步骤
/**
创建小根堆(向上调整)
*/
void createHeap(Heap* heap, HeapDataType* arr, unsigned int len, Compare com) {
	if (heap == NULL)
		return;

	for (int i = 0; i < len; i++) {
		heap->array[i] = arr[i];
		heap->size++;
	}

	// 找到零界点
	int flag = (len - 1) / 2;

	flag--;
	while (flag >= 0) {
		int parrent = flag;
		while (1) {

			int child = parrent * 2 + 1;
			if (child >= len)
				break;
			if (child + 1 >= len) {
				if (com(heap->array[child], heap->array[parrent])) {
					swap(&heap->array[child], &heap->array[parrent]);
					parrent = child;
					break;
				}
				else {
					break;
				}
			}

			// 找最大/小的左右孩子
			if (!com(heap->array[child], heap->array[child + 1])) {
				child++;
			}

			// 将当前节点和最大/小的孩子比较,如果比最大/小的孩子小/大则交换。
			if (com(heap->array[child], heap->array[parrent])) {
				swap(&heap->array[child], &heap->array[parrent]);
				parrent = child;
			}
			else {
				break;
			}
		}
		flag--;
	}
}


向堆中插入元素

步骤:

  1. 将元素放到堆尾(数组的最后)
  2. 将该元素向上调整
// 向堆中插入元素(向上调整)
void insertIntoHeap(Heap* heap, HeapDataType insertData, Compare com) {

	// 将元素放入堆尾
	heap->size++;
	heap->array[heap->size - 1] = insertData;

	if (heap->size == 1)
		return;

	int child = heap->size - 1;
	while (1) {
		int parrent = (child - 1) / 2;

		//如果当前元素比父元素小,就向上移动
		if (com(heap->array[child], heap->array[parrent])) {
			swap(&(heap->array[child]), &(heap->array[parrent]));
			child = parrent;
			if (parrent == 0)
				break;
		}
		else {
			break;
		}
	}
}


打印堆的元素

// 打印数组元素
void printHeap(Heap* heap) {
	int sum = 1;
	int j = 0;
	for (int i = 0; i < heap->size; i++) {
		if (i == sum - 1)
			for (int j = 0; j < heap->size - i; j++) {
				printf(" ");
			}
		else
			printf(" ");
		
		printf("%d", heap->array[i]);
		j++;
		if (sum == j) {
			printf("\n");
			sum *= 2;
			j = 0;
		}
		else if (i == 0)
			printf("\n");
	}
	printf("\n");
}


获取堆顶元素

获取数组的第0个元素

HeapDataType getHeapTop(Heap* heap) {
	if (!isEmptyHeap)
		return heap->array[0];
	return -1;
}

删除堆顶元素

步骤:

  1. 将最后一个元素赋值给第一个元素。
  2. 删除最后一个元素
  3. 对堆顶元素进行向下调整
// 删除堆顶元素
void deleteFromHeap(Heap* heap, Compare com) {
	if (heap == NULL)
		return;
	if (isEmptyHeap(heap))
		return;
	heap->size--;
	// 将最后一个元素赋值给第一个元素
	heap->array[0] = heap->array[heap->size];

	// 将根元素赋值给parrent
	int parrent = 0;
	// 向下调整
	while (1) {
		int child = parrent * 2 + 1;
		if (child >= heap->size)
			break;
		if (child + 1 >= heap->size) {
			if (com(heap->array[child], heap->array[parrent])) {
				swap(&heap->array[parrent], &heap->array[child]);
				parrent = child;
			}
			else {
				break;
			}
		}
		if (!com(heap->array[child], heap->array[child + 1])) {
			child++;
		}
		if (com(heap->array[child], heap->array[parrent])) {
			swap(&heap->array[parrent], &heap->array[child]);
			parrent = child;
		}
		else {
			break;
		}
	}
}


判断是不是空堆

int isEmptyHeap(Heap* heap) {
	return heap->size == 0 ? 1 : 0;
}

交换两个元素

void swap(HeapDataType* data1, HeapDataType* data2) {
	HeapDataType tmp = *data1;
	*data1 = *data2;
	*data2 = tmp;
}

小根堆的向下调整

由于调整的左右子树已经是一个堆了,只需要对堆顶元素进行向下调整即可

// 小根堆的向下调整
void topDownHeap(Heap* heap, int size, Compare com) {
	if (size == 0)
		return;
	int parrent = 0;
	int child = 0;
	while (1) {
		child = parrent * 2 + 1;
		if (child > size)
			break;
		if (child + 1 > size) {
			if(com(heap->array[child], heap->array[parrent]))
				swap(&heap->array[parrent], &heap->array[child]);
			break;
		}
		// 找到两个孩子之间比较大的
		if (!com(heap->array[child], heap->array[child + 1])) {
			child++;
		}
		// 父节点和最大的孩子比较,小于最大孩子,则交换
		if (com(heap->array[child], heap->array[parrent])) {
			swap(&heap->array[parrent], &heap->array[child]);
			parrent = child;
		}
		else {
			break;
		}
	}
}

堆排序

  1. 将堆顶元素和最后一个元素(下标为n)交换;
  2. n--;
  3. 对前n - 1个元素进项向下调整(堆顶的向下调整)
  4. 继续1,直到n == 0
// 堆排序,从大到小
void heapSort(Heap* heap, Compare com) {
	int end = heap->size - 1;
	while (end > 0) {
		swap(&heap->array[0], &heap->array[end]);
		--end;
		// 调整
		topDownHeap(heap, end, com);
	}
}


数据查找(从很多个数里面查找最大的K个数)

步骤

  1. 将堆的前K个数插入小项堆中
  2. 插入后n - k个数据,每次都比较准备插入的数据和堆顶的大小。如果大于堆顶,则替换堆顶,并对堆顶进行向下调整。
// 数据查找(从很多个数里面查找最大或者最小的K个数)
void getDataFromGreatData(HeapDataType* arr, unsigned int len, unsigned int k, Compare com) {

	Heap* heap = (Heap*)malloc(sizeof(Heap));
	if (heap == NULL || k == 0 || len <= k)
		return;
	initHeap(heap);

	if (len <= k) {
		// 将前len个数插入堆中
		createHeap(heap, arr, len, com);
		return;
	}

	// 将前K个数插入堆中
	createHeap(heap, arr, k, com);
	
	for (int i = k; i < len; i++) {
		// 获取堆顶元素
		HeapDataType top = getHeapTop(heap);
		if (top < arr[i]) {
			deleteFromHeap(heap, com);
			insertIntoHeap(heap, arr[i], com);
		}
	}

	printHeap(heap);
}

测试用例:

int main() {
	Heap* heap = (Heap*)malloc(sizeof(Heap));
	if (heap == NULL)
		return 0;
	initHeap(heap);
	HeapDataType arr[] = {53, 17, 78, 9, 45, 65, 87, 23, 31};
	createHeap(heap, arr, sizeof(arr)/sizeof(arr[0]), Greater);
	insertIntoHeap(heap, 5, Greater);
	insertIntoHeap(heap, 50, Greater);
	insertIntoHeap(heap, 13, Greater);
	deleteFromHeap(heap, Greater);
	printf("构建堆\n");
	printHeap(heap);
	printf("\n获取堆中5个最大/小的元素\n");
	getDataFromGreatData(heap->array, heap->size, 5, Greater);
	printf("\n堆排序\n");
	heapSort(heap, Greater);
	printHeap(heap);
	printf("\n");
	
	
	return 0;
}

运行截图:

小根堆

数据结构-堆


大根堆:

数据结构-堆

完整代码在Git:github.com/Niceug