题12

题12

题目

堆排序分为两个阶段: 第一阶段将给定的序列构造成一个初始堆, 第二阶段逐次输出堆顶元素,并调整使其保持堆的性质.
设有给定序列 ,若在堆排序的第一阶段将该序列构造成一个大根堆, 则交换元素的次数为 ( ).
A. 5 B. 6 C. 7 D. 8

分析

输出堆排序序列，需要把堆顶元素弹出去，这个弹出通过和最后一个元素交换来实现，也就是a[1]=a[cnt--]，然后下沉这个新的栈顶元素，使得这个堆有序

解

B

• 初始序列是一棵顺序存储的完全二叉树
• 然后根据大根堆的要求, 按照从下到上、从右到左的顺序进行调整
  • 98 和 77 比较, 98 和 77 交换 (交换 1 次)
  • 14 和 35 比较, 35 和 35 比较, 不交换
  • 98 和 55 比较, 98 和 62 比较, 98 和 62 交换 (交换 1 次)
  • 62 和 77 比较, 77 和 62 交换 (交换 1 次)
  • 98 和 35 比较, 98 和 48 比较, 98 和 48 交换 (交换 1 次)
  • 77 和 55 比较, 77 和 48 比较, 77 和 48 交换 (交换 1 次)
  • 48 和 62 比较, 62 和 48 交换 (交换 1 次)
• 一共交换 6 次