【C语言数据结构】堆

• 堆
• 一、堆
• 二、堆调整示意图
• 三、堆应用之构造哈夫曼树
• 四、哈夫曼编码

#include 
#include 

typedef int ElemType;

typedef struct{
	ElemType *data;
	int size;
	int capacity;		
}heap; 

void BuildMaxHeap(ElemType A[], int len); // 创建一个最大堆 
void HeadAdjust(ElemType A[], int k, int len);	// 堆向下调整 


// 创建一个最大堆
void BuildMaxHeap(ElemType A[], int len) {
	for (int i = len / 2 ; i > 0 ; i--) {
		HeadAdjust(A, i, len);
	} 
} 

// 堆向下调整 
void HeadAdjust(ElemType A[], int k, int len) {
	A[0] = A[k];
	// 需要有等号 
	for (int i = 2 * k; i <= len; i = i * 2) {
		if (i 
			i++;
		} 
		if (A[0] >= A[i]) {
			break;
		} else {
			A[k] = A[i];
			k = i;
		}
	} 
	A[k] = A[0];
} 

int main(){
	heap h;
	printf("请输入堆的长度 容量：");
	scanf("%d %d", &(h.size), &(h.capacity));
	h.data = (ElemType *)malloc((h.capacity + 1) * sizeof(ElemType));
	h.data ++;
	for (int i = 0; i < h.size; i++) {
		scanf("%d", (h.data) + i);
	}
	h.data --;
	BuildMaxHeap(h.data, h.size);
	for (int i = 1; i <= h.size; i++) {
		printf("%d ", *(h.data + i));
	}
	free(h.data);
	return 0;
}