经历良久终于明白了其中的弯弯绕绕,特以此笔记
- 堆排序中交换位置, 实际上交换的是对应的下标
- a, b 表示的是h数组中实际的位置, h[3] = x, h[4] = y;
- 题目要求第k次插入,那么需要找到第k次插入对应的数组下标 ph[5] = 3, ph[7] = 4;
- 当前下标对应的是哪次插入呢 hp[3] = 5, hp[4] = 7;
交换过程
- 两个元素要交换,那么对应的h数值是需要交换的
- 给定数组下标a, b; swap(h[a] , h[b]);
- 第k次插入的数组的下标需要交换,那么下标a,b队对应的是多少次的插入呢,所以需要新数组hp
- hp[a], hp[b]; 表示的是下标a, b对应的多少次插入
- swap(ha[a], hp[b]);
- 交换k次插入对应的实际下标 swap(ph[hp[a]], ph[hp[b]]);
- 5,6两步骤 需要先执行6,再执行5, 因为5会改变对应的hp[a];