所以我要为类编写一个堆数据结构,它应该只使用插入和删除操作来实现堆排序。
它有效。。对于较小的int集(大小为10及以下(。然而,当我在中输入一大组数字(100+(时,结果只是半排序的。。
这是我的插入方法:
void insert(heapHndl H, int priority) {
// Makes sure heap has enough room for new element.
assert(!isFull(H));
// Increase the current size.
H->currentSize++;
// Add to array.
int pos = H->currentSize;
// Work up.
while (pos > 1 && priority < H->array[pos/2]) {
swap (H, pos, pos/2);
pos /= 2;
}
H->array[pos] = priority;
}
这是我的删除方法:
void deleteMax(heapHndl H) {
// Makes sure the heap is not empty.
assert(!heapEmpty(H));
int root = 1;
// Swap the root and last element.
swap(H, root, H->currentSize);
H->array[H->currentSize] = -1;
H->currentSize--;
// Work your way down from the root.
while(root != H->currentSize) {
int leftChild = 2*root;
int rightChild = 2*root + 1;
int minChild;
// If root is smaller than children..
if (H->array[root] <= H->array[leftChild] &&
H->array[root] <= H->array[rightChild])
break;
// If at a leaf node.
if (rightChild > H->currentSize){
if (leftChild >= H->currentSize)
break;
else minChild = leftChild;
} else {
// Determines which child to swap with.
if (H->array[leftChild] <= H->array[rightChild])
minChild = leftChild;
else minChild = rightChild;
}
swap(H, root, minChild);
root = minChild;
}
}
这是heapHndl。
typedef struct HeapStruct {
int maxSize;
int currentSize;
int *array;
} HeapStruct;
typedef HeapStruct* heapHndl;
我似乎不知道delete方法还缺少哪些情况。我确信我的插入方法是好的(手动检查(。谢谢你的帮助。编辑:忽略名称,deleteMax。它实际上是一个最小的堆。根是最小的整数。
以下两行肯定是的问题
if (leftChild > H->currentSize || rightChild > H->currentSize)
break;
如果其中一个孩子不见了,循环不允许中断,只有当两个孩子都不见了。如果右边的孩子不见了,你仍然必须检查,并可能与左边的孩子交换。
编辑:另一方面,如果父节点是三个节点中最小的一个(父节点、左节点、右节点(,则循环确实需要中断。