由于自己理解的ph数组和hp数组比较麻烦,所以决定分享出来,帮助大家理解!!!
heap_swap操作
heap_swap操作是干什么的?它是为了删除了一个元素(堆顶/任意元素)而服务的。只需要把想要删除的元素和堆的最后一个元素互换,然后堆的大小减1,就完成删除操作,接下来只需要维护堆即可。同时写上up操作和down操作,就完成了维护。这里这两个操作只会执行一个,因为是看互换过来的元素是否满足小根堆的性质来执行up操作或者down操作的
ph数组
由于题目的第四、第五操作涉及了第k个插入的数。但是我们的h数组只存了元素,并不知道哪一个元素是第几个插入的数,所以我们需要一个数组来存储第几个插入的数在堆里面的下标是什么,这个自然就是我们说的ph数组了。
用法也只有一个就是,ph[k] = i;表示第k个插入的数在堆里面的下标为i。
hp数组
可能很多人都有一个疑惑,ph数组已经记录了插入的顺序,貌似可以做一切能做的,并不需要什么了。但是,事实并不是这样的。
当我们交换了在堆里面下标为a、b这两个元素后,此时ph数组记录的插入顺序就错了,因为堆里面元素互换了。要想让ph数组正确,就需要互换ph[a],ph[b]。而要互换ph数组,就必须ph数组中的哪两个记录a、b的插入顺序。这时候你们可能会说,ph数组不是已经记录了吗?没错,ph数组是记录了,但是它是单向的,是ph数组指向堆元素下标的,而我们只知道堆元素的下标,我们怎么可能知道ph数组中的哪两个指向的a、b呢?所以必须开一个数组来存储堆里面下标为的元素是第几个插入的。使它们是双向的,这样才能互换ph数组。hp数组就是为了互换ph数组而服务的