任何按最直观的方式去定位这个待修改的元素?
不是特别清楚斑竹的意思。
不是特别清楚斑竹的意思。
[此贴子已经被作者于2007-10-13 0:24:37编辑过]
以下是引用aipb2007在2007-10-12 22:59:15的发言：
随便引申一个问题，这也是我最近写一个优先级队列模版时遇到的。
increase_key(int i,int key){//将节点i的值改变为key
这个操作，参数i表示堆中第i个元素，这里也就是data[i]
我的问题是，实际在用户使用这个接口时，他不会在意第i个元素在堆中是什么，因为那时我们封装的实现机制。
用户想改变一个元素的key值，最直接的是来自原始输入，举个例子：
输入 5 3 4 6 9
某一时刻堆中，也就是data中是9 5 3 4 6
用户要修改5为7的话，最直接的是increase_key(5,7），或者increase_key(0,7)
其中后者是原始输入的顺序号，然而对data中5的位置1是不可见，也是不必要知道的。
我的问题是任何按最直观的方式去定位这个待修改的元素。
————————————————————————
ps : 表达清楚没，不知！
随便引申一个问题，这也是我最近写一个优先级队列模版时遇到的。
increase_key(int i,int key){//将节点i的值改变为key
这个操作，参数i表示堆中第i个元素，这里也就是data[i]
我的问题是，实际在用户使用这个接口时，他不会在意第i个元素在堆中是什么，因为那时我们封装的实现机制。
用户想改变一个元素的key值，最直接的是来自原始输入，举个例子：
输入 5 3 4 6 9
某一时刻堆中，也就是data中是9 5 3 4 6
用户要修改5为7的话，最直接的是increase_key(5,7），或者increase_key(0,7)
其中后者是原始输入的顺序号，然而对data中5的位置1是不可见，也是不必要知道的。
我的问题是任何按最直观的方式去定位这个待修改的元素。
————————————————————————
ps : 表达清楚没，不知！
对于increase_key(5,7）这种，就直接在堆中找到5，替换成7就行，如果里面有多个5，找第一个替换然后就退出
对于increase_key(0,7)这种，那就把原数组备份一下，找到data[0]的值，再到堆里找第一个同样值的元素替换掉，或者把下表存为一个数组，元素每交换一次，下标也交换一次，这样就能根据原来的下表找到现在的下标了。总之就是用空间的花销来实现。
