【数据结构与算法】第8课—数据结构之二叉树(堆)-3. 实现顺序结构二叉树

3.1 堆的概念

• 堆是一种特殊的二叉树，也是完全二叉树，一般是把堆使用顺序结构来存储
• 堆的底层结构是数组
• 堆也有大堆和小堆之分，根节点最大的堆叫最大堆/大根堆，根节点最小的堆叫最小堆/小根堆

---

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

• 二叉树的性质
• 对于有N个节点的完全二叉树，对于在下标0~k的数组中有：

---

3.2 堆的实现

3.2.1 堆的数据结构

typedef int HeapDataType;
//堆的数据结构
typedef struct Heap
{
	HeapDataType* arr; //动态数组
	int size;          //数组有效数据个数
	int capacity;      //数组容量大小
}Heap;

3.2.2 堆的初始化

//堆初始化
void HeapInit(Heap* pheap)
{
	assert(pheap);
	pheap->arr = NULL;
	pheap->size = pheap->capacity = 0;
}

3.2.3 堆插入数据

---

//交换值
void Swap(HeapDataType* p1, HeapDataType* p2)
{
	HeapDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

//向上调整算法
void AdjustUp(HeapDataType* arr, HeapDataType child)
{
	int parent = (child - 1) / 2;  //定义父节点
	while (child > 0)
	{
		//小堆
		if (arr[child] < arr[parent])
		{
			Swap(&arr[child], &arr[parent]); //交换值
			child = parent;  //child走到父节点
			parent = (child - 1) / 2;  //parent走到更新后的child的父节点
		}
		else
			break;
	}
}

//堆插入数据
void HeapPush(Heap* pheap, HeapDataType x)
{
	assert(pheap);
	//如果数组满了/为空
	if (pheap->size == pheap->capacity)
	{
		//定义数组容量
		int newCapacity = pheap->capacity == 0 ? 4 : 2 * pheap->capacity;
		//为数组申请空间
		HeapDataType* tmp = (HeapDataType*)realloc(pheap->arr, sizeof(HeapDataType) * newCapacity);
		if (tmp == NULL)
		{
			perror("realloc");
			exit(1);
		}
		pheap->arr = tmp;  //申请的空间赋给数组
		pheap->capacity = newCapacity;  //新容量大小赋给capacity
	}
	//插入数据
	pheap->arr[pheap->size] = x;
	//向上调整
	AdjustUp(pheap->arr, pheap->size);
	pheap->size++;
}

3.2.4 删除堆顶数据

---

---

---

---

//交换值
void Swap(HeapDataType* p1, HeapDataType* p2)
{
	HeapDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
//向下调整算法
void AdjustDown(HeapDataType* arr, HeapDataType parent, int n)
{
	HeapDataType child = parent * 2 + 1;//孩子节点
	while (child < n)
	{
		//找最大的孩子节点
		if (child + 1 < n && arr[child] < arr[child + 1])
		{
			child++;
		}
		//如果子节点大于父节点(大堆)
		if (arr[child] > arr[parent])
		{
			//交换父节点和子节点
			Swap(&arr[child], &arr[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
			break;
	}
}

//删除堆顶数据
void HeapPop(Heap* pheap)
{
	assert(!HeapEmpty(pheap));
	//交换堆顶元素和最后一个元素
	Swap(&pheap->arr[0], &pheap->arr[pheap->size - 1]);
	pheap->size--;
	//向下调整
	AdjustDown(pheap->arr, 0, pheap->size);
}

//取堆顶数据
HeapDataType HeapTop(Heap* pheap)
{
	assert(pheap);
	return pheap->arr[0];
}

3.2.5 堆的判空和求有效数据个数

//判空
bool HeapEmpty(Heap* pheap)
{
	assert(pheap);
	return pheap->size == 0;
}

//求有效数据个数
int HeapSize(Heap* pheap)
{
	assert(pheap);
	return pheap->size;
}

3.3 堆排序

• 先建堆

---

• 之所以升序要建大堆，是因为最后还需要将堆顶元素与最后元素交换，然后向下调整，具体操作如下：

---

• 排序(升序)
• 向下调整算法

---

• 堆排序时，每次首尾交换元素后，最后一个元素就是数的最大元素，因此在向下调整的过程中，child的限制条件为child<end,也就说明child移动的过程中是不会到划定范围内的最后一个元素，因为那样child已经越界了，这样也就保证了首尾每次交换的都是划定范围内的最大元素，同理child的兄弟节点child+1<end，也要保证不能越界，end每次向下调整过后要-1

---

---

//堆排序
void HeapSort(HeapDataType* arr, int sz)
{
	//根据给定的arr建大堆
	//child--sz-1  parent--(sz-1-1)/2
	for (int i = (sz - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(arr, i, sz);
	}
	
	//排升序：建大堆
	//排降序：建小堆
	//堆排序
	int end = sz - 1;
	while (end)
	{
		Swap(&arr[0], &arr[end]);
		AdjustDown(arr, 0, end);
		end--;
	}

}

int main()
{
	int arr[] = { 34,18,88,23,67,45 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	HeapSort(arr,sz);//堆排序
	return 0;
}

• 向下调整算法的时间复杂度：O(logn),n为元素个数
• 堆排序的时间复杂度：n*O(logn),n为元素个数，因为堆排序在建堆时要执行（sz-2）次向下调整算法

• 向上调整(升序)

//向上调整算法
void AdjustUp(HeapDataType* arr, HeapDataType child)
{
	int parent = (child - 1) / 2;  //定义父节点
	while (child > 0)
	{
		//大堆
		if (arr[child] > arr[parent])
		{
			Swap(&arr[child], &arr[parent]); //交换值
			child = parent;  //child走到父节点
			parent = (child - 1) / 2;  //parent走到更新后的child的父节点
		}
		else
			break;
	}
}
//堆排序
void HeapSort(HeapDataType* arr, int sz)
{
	//根据给定的arr建大堆
	//child--sz-1  parent--(sz-1-1)/2
	//for (int i = (sz - 1 - 1) / 2; i >= 0; i--)
	//{
	//	AdjustDown(arr, i, sz); //向下调整算法
	//}

	//向上调整算法
	for (int i = 0; i < sz; i++)
	{
		AdjustUp(arr, i);
	}
	
	//排升序：建大堆
	//排降序：建小堆
	//堆排序
	int end = sz - 1;
	while (end)
	{
		Swap(&arr[0], &arr[end]);
		AdjustDown(arr, 0, end);
		end--;
	}
	for (int j = 0; j < sz; j++)
	{
		printf("%d ", arr[j]);
	}
}

• 总结
• 向上调整算法建堆的时间复杂度为O(n*logn)
• 向下调整算法建堆的时间复杂度为O(n)
• 堆排序的时间复杂度为O(nlogn)

3.4 Top K问题

---

• 代码实现

//造数据
void CreateNdata()
{
	int n = 100000;
	srand((unsigned int)time(NULL));
	FILE* fin = fopen("data.txt", 'w');
	if (fin == NULL)
	{
		perror("fopen fail!\n");
		return;
	}
	for (int i = 0; i < n; i++)
	{
		int x = (rand() + i) % 1000000;
		fprintf(fin, "%d\n", x);
	}
	fclose(fin);
}

//求前k个数据
void TopK()
{
	int k = 0;
	printf("请输入k:");
	scanf("%d", &k);

	const char* file = "data.txt";
	FILE* fout = fopen(file, 'r');
	if (fout == NULL)
	{
		perror("fout");
		exit(2);
	}
	//找最大的前K个数,建小堆
	int* minHeap = (int*)malloc(k * sizeof(int));
	if (minHeap == NULL)
	{
		perror("malloc");
		exit(1);
	}
	//读取文件中的前k个数据建堆
	for (int i = 0; i < k; i++)
	{
		fscanf(fout, "%d", &minHeap[i]);
	}
	//建堆
	for (int i = (k - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(minHeap, i, k);
	}
	//遍历剩下的n-k个数据，跟堆顶数据比较，谁大谁入堆
	int x = 0;
	while (fscanf(fout, "%d", &x) != EOF)
	{
		if (x > minHeap[0])
		{
			minHeap[0] = x;
			AdjustDown(minHeap, 0, k);
		}
	}
	for (int i = 0; i < k; i++)
	{
		printf("%d ", minHeap[i]);
	}
	fclose(fout);
	free(minHeap);
	minHeap = NULL;
}