大顶堆调整-创新互联

已知关键字序列（k1,k2,…,kn-1）是大顶堆，试编写算法实现将（k1,k2,…,kn-1,kn）调整为大顶堆，假设n大值为20。

输入一个大顶堆序列k1 k2 …kn-1，数值类型为整型，以空格分隔数据，回车结束。
输入kn值。

输出k1,k2,…,kn-1,kn调整为大顶堆后的序列，数据之间以空格分隔。

100 90 80 60 85 75
101

101 90 100 60 85 75 80

#includeusing namespace std;
void Pushdown(int first, int last, int A[]) {int r = first;
	while (r<= last / 2)   //A[r]是叶子节点则退出循环
		if (r == last / 2 && last % 2 == 0) {//A[r]有且仅有一个左儿子
			if (A[r]< A[2 * r])  swap(A[r], A[2 * r]);
			r = last;
		}
		else if (A[r]< A[2 * r] && A[2 * r] >= A[2 * r + 1]) {//A[r]的左儿子<= A[r]的右儿子，且小于A[r]
			swap(A[r], A[2 * r]);
			r *= 2;
		}
		else if (A[r]< A[2 * r + 1] && A[2 * r + 1] >A[2 * r]) {//A[r]的右儿子< A[r]的左儿子，且小于A[r]
			swap(A[r], A[2 * r + 1]);
			r = 2 * r + 1;
		}
		else  r = last;
}
int main() {int temp, cnt = 1, A[20];
	char eat = '\0';
	while (eat != '\n') {scanf("%d%c", &temp, &eat);
		A[ cnt++] = temp;
	}
	cin >>A[cnt];
	for (int i = cnt / 2; i >= 1; i--) {Pushdown(i, cnt, A);
	}
	for (int i = 1; i< cnt+1; i++)  cout<< A[i]<< " ";
	return 0;
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧