【数据结构】二叉树的顺序存储、堆的实现及其应用：堆排序与Top-K问题

typedef int HPDataType; 
typedef struct Heap
{
	HPDataType* _a;
	int _size;
	int _capacity;
}Heap;

void HeapInit(Heap* hp) {
	assert(hp);
	hp->_a = NULL;
	hp->_size = 0;
	hp->_capacity = 0;
}

void HeapDestroy(Heap* hp) {
	assert(hp);
	free(hp->_a);
	hp->_a = NULL;
	hp->_size = hp->_capacity = 0;
}

void HeapCheckCapacity(Heap* hp) {
    assert(hp);
    if (hp->_size == hp->_capacity) 
    {
        int newCapacity = hp->_capacity == 0 ? 4 : hp->_capacity * 2;
        HPDataType* tmp = (HPDataType*)realloc(hp->_a, 
                                        newCapacity * sizeof(HPDataType));
        if (tmp == NULL) {
            perror("realloc fail");
            exit(-1);
        }
        hp->_a = tmp;
        hp->_capacity = newCapacity;
    }
}

HPDataType HeapTop(Heap* hp) 
{
	assert(hp);
	assert(!HeapEmpty(hp));
	return hp->_a[0];
}

int HeapSize(Heap* hp) 
{
	assert(hp);
	return hp->_size;
}

bool HeapEmpty(Heap* hp) 
{
	assert(hp);
	return hp->_size == 0;
}

void Swap(int* x, int* y)
{
	int tmp = *x; 
	*x = *y;
	*y = tmp;
}
//向上调整算法
void AdjustUp(int* a, int n)//需要调整的是最后一个
{
	int child = n - 1;
	while (child > 0)//新插入的点成为根节点后就不用比较
	{
		int parents = (child - 1) / 2;
		if (a[child] < a[parents])
		{
			Swap(&a[child], &a[parents]);
			child = parents;//新插入的点来到双亲结点
		}
		else
			break;
	}
}

void HeapPush(Heap* hp, HPDataType x) {
    assert(hp);
    // 1. 检查容量
    HeapCheckCapacity(hp);
    // 2. 将新元素插入到堆的末尾
    hp->_a[hp->_size] = x;
    hp->_size++;
    // 3. 对最后一个元素进行向上调整，保持堆结构
    AdjustUp(hp->_a, hp->_size - 1);
}

int arr[] = {27,15,19,18,28,34,65,49,25,37};

//向下调整算法 
// a: 堆数组
// n: 堆的大小（数组有效长度）
// root: 需要调整的节点的下标（从这个节点开始向下调整）
void AdjustDown(int* a, int n, int root)
{
	int parent = root;
	int child = parent * 2 + 1; // 默认先指向左孩子

	// 当孩子索引还在堆数组范围内时，继续调整
	while (child < n)
	{
		// 1. 选出左右孩子中较小的那一个
		// 如果右孩子存在，且右孩子比左孩子小，则让child指向右孩子
		if (child + 1 < n && a[child + 1] < a[child])
		{
			child++;
		}
		// 2. 比较双亲节点和较小的孩子
		if (a[child] < a[parent])
		{
			// 如果孩子比双亲小，则交换它们的内容
			Swap(&a[child], &a[parent]);
			// 继续向下调整：双亲指针下沉到孩子的位置
			parent = child;
			// 计算新的左孩子位置
			child = parent * 2 + 1;
		}
		else
		{
			// 如果双亲已经比两个孩子都小了，说明调整完成，满足堆的性质
			break;
		}
	}
}

// 堆的删除（删除堆顶元素）
void HeapPop(Heap* hp) {
    assert(hp);
    assert(!HeapEmpty(hp)); // 堆不能为空
    
    // 1. 将堆顶元素与最后一个元素交换
    Swap(&hp->_a[0], &hp->_a[hp->_size - 1]);
    // 2. 删除最后一个元素（也就是原来的堆顶）
    hp->_size--;
    // 3. 对新的堆顶元素进行向下调整，保持堆结构
    AdjustDown(hp->_a, hp->_size, 0);
}

// 堆的构建
void HeapCreate(Heap* hp, HPDataType* a, int n) 
{
    assert(hp && a);
    assert(n >= 0);

    // 1. 使用已有的初始化函数
    HeapInit(hp);
    
    if (n == 0) {
        return;
    }

    HeapCheckCapacity(hp); 

    // 2. 拷贝数据
    memcpy(hp->_a, a, n * sizeof(HPDataType));
    hp->_size = n;

    // 3. 构建堆：从最后一个非叶子节点开始向下调整
	// 最后一个非叶子节点的索引 = (n-1-1)/2 = (n-2)/2
    for (int i = (n - 1 - 1) / 2; i >= 0; i--) 
    {
        AdjustDown(hp->_a, n, i);
    }
}

int a[] = {1,5,3,8,7,6}; 

void HeapSort(int* a, int n)
{
	//建堆
	for (int i = (n - 2) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}
	//排序
	for (int i = n - 1; i > 0; i--)
	{
		Swap(&a[0], &a[i]);//首尾交换
		AdjustDown(a, i , 0);//对剩余的进行调整，即对未排序的进行调整
	}
}

void PrintTopK(int k)
{
	int* a = (int*)malloc(k * sizeof(int));
	if (a == NULL)
		return;
	FILE* pf = fopen("data.txt", "r");
	if (pf == NULL) {

		perror("opening file");
		return;
	}
	for (int i = 0; i < k; i++)
	{
		fscanf(pf, "%d", &a[i]);
	}	
	
	//建堆
	for (int i = (k - 2) / 2; i >= 0; i--)
	{
		AdjustDown(a, i, k);
	}
	//调整
	int x = 0;
	for (int i = k; i < 10000; i++)
	{
		fscanf(pf, "%d", &x);
		if (x > a[0])
		{
			a[0] = x;
			AdjustDown(a, 0, k);
		}
	}
	//打印
	//注意：这里打印的结果不是有序的，因为堆只保证堆顶最小，并不保证整体有序。
	for (int i = 0; i < k; i++)
	{
		printf("%d ", a[i]);
	}
}