P**********c
发帖数: 3417 | 1 保证heap的property, 有什么好的方法没有？ | g*****k
发帖数: 623 | 2 先bubble up，也就是swap(current, parent)直到root,
然后就跟删root的操作一样了，我没怎么仔细检查，但是应该没什么问题。
你不妨写写代码测试一下，回来报告一下，呵呵。
【在 P**********c 的大作中提到】
: 保证heap的property, 有什么好的方法没有？
| s****n
发帖数: 48 | 3 heap有什么property?不就是root节点特别一点吗？把最后一个元素移到被删除节点，
heap size减一不就行了吗？
Am I missing something? | P**********c
发帖数: 3417 | 4 heap是recursive定义的，每个子树也必须是heap，直接size--肯定不行的. 不过你这个也是一个思路，可以把最后一个元素移到被删除节点，然后再怎么调整一下。
但是如果被删除的点跟最后一个节点不是属于一个子树的话，貌似不太好处理。getback的那个思路应该是对的。我待会儿试下。
比如这样一个heap
10
9 2
8 7 1 0
6
你这个思路的话，如果删除的是9，那应该把6移到9的位置上然后siftdown, 如果删除的是1， 移过去之后需要siftup, 所以需要分情况讨论。
【在 s****n 的大作中提到】
: heap有什么property?不就是root节点特别一点吗？把最后一个元素移到被删除节点，
: heap size减一不就行了吗？
: Am I missing something?
| P**********c
发帖数: 3417 | 5 测过了，这个应该是对的。
【在 g*****k 的大作中提到】
: 先bubble up，也就是swap(current, parent)直到root,
: 然后就跟删root的操作一样了，我没怎么仔细检查，但是应该没什么问题。
: 你不妨写写代码测试一下，回来报告一下，呵呵。
| Y********f
发帖数: 410 | 6 测试过的代码：
#include
#include
using namespace std;
void deleteNode(int heap[], int n, int pos)
{
// put the last elements to where the node removed
heap[pos] = heap[n-1];
// adjust elements above pos
int i = pos;
while(i != 0 && heap[i] < heap[(i - 1) / 2])
{
swap(heap[i], heap[(i - 1) / 2]);
i = (i - 1) / 2;
}
// adjust elements below pos
i = pos;
while(true)
{
if (2 * i + 1 > n -2)
{
//already leaf
break;
}
else if (2 * i + 1 == n -2)
{
//only one leaf child
if (heap[2 * i + 1] > heap[n - 2])
{
swap(heap[2 * 1 - 1], heap[n - 2]);
}
break;
}
else
{
// two children
int minChild = 0;
if (heap[2 * i + 1] < heap[2 * i + 2])
{
minChild = 2 * i + 1;
}
else
{
minChild = 2 * i + 2;
}
if (heap[i] > heap[minChild])
{
swap(heap[i], heap[minChild]);
i = minChild;
}
else
{
break;
}
}
}
}
void print_heap(int heap[], int n)
{
int rntPos = 1;
for (int cnt = 0; cnt < n; cnt++)
{
if (cnt == rntPos)
{
cout << endl;
rntPos = rntPos * 2 + 1;
}
cout << heap[cnt] << " ";
}
}
int main()
{
{
int heap[] = {2, 9, 3, 11, 25, 6, 12, 14, 13, 27, 28, 7};
int numElms = sizeof(heap)/sizeof(int);
print_heap(heap, numElms);
deleteNode(heap, numElms, 4);
cout << endl << " ------" << endl;
print_heap(heap, numElms - 1);
}
cout << endl << endl;
{
int heap[] = {2, 9, 3, 11, 25, 6, 12, 14, 13, 27, 28, 7};
int numElms = sizeof(heap)/sizeof(int);
print_heap(heap, numElms);
deleteNode(heap, numElms, 2);
cout << endl << " ------" << endl;
print_heap(heap, numElms - 1);
}
}
【在 P**********c 的大作中提到】
: 保证heap的property, 有什么好的方法没有？
| n****r
发帖数: 120 | 7 假设heap是max Heap。
可以直接对要删除的节点i和最后的节点N交换，然后
1.若要删除的节点比最后节点小，执行siftUp，否则siftDown
2.删除最后的节点
这样应该就可以，不需要先和根节点交换 |
|
