I am trying to implement the removal of an arbitrary element from the pyramid. That is, we are given the index of the element in the array that contains the pyramid, and we have to delete it. In theory, the algorithm is as follows: put the last element in place of the last element and start either sieving down (sift_down) or sieving up (sift_up). At first I thought that it was necessary to perform only the sieving down, then I decided to launch both sift_down (i) and sift_up (i), where i is the element that is being removed and in which place the last element was put. That's how I do about it.

heap[i] = heap[--heap_size]; // Ставим последний элемент на место удаляемого sift_down(i); // Просеивание вниз sift_up(i); // Просеивание вверх

But this algorithm does not work for me on many tests (I don’t know on which ones, I just know the verdict - Wrong answer). Tell me how to properly restore the pyramid after putting the last element in place of the deleted element.

ZY I solve the problem from here (page 12, task 5).

  • Please send sift_down (i); and sift_up (i); - hedgehogues
  • Here is the complete task code. There it turns out requests of three types, the third type is just the removal of an arbitrary element. Prior to this, I solved the problem for processing only requests 1, 2 and passed. I have already tried everything but I can’t pass the task completely. ideone.com/3tGmeA - moskalenco_a

1 answer 1

I think the problem here is that when sifting down, we cannot use shift_down (...) in its pure form, since there is ambiguity: which element should be changed. I will give an example:

Example

Obviously, in this case there is some ambiguity. Suppose that the last element is equal to 7. Then we can exchange 7 and 8, or exchange places 6 and 7. In the first case, obviously, the structure of the heap will not be broken. In the second, it turns out that one of the definition points will be wrong, since "every descendant must be less than the parent", since we have a maximum in the root (or, if there is a minimum in the root, every descendant must be more than the parent). In this case, an example is given when the maximum is at the root.

In this case, when sifting down, you need to check both the element 2 * i + 1 and 2 * i , choosing the right one among them.

It is clear that when sifting up this does not occur, since the ancestor of the node is only one. The choice is unequivocal.

  • I just check both elements in sift_down, in 11-12 lines in the code you can look at ideone. Only the numbering is from scratch and therefore I check the elements 2 * i + 1 and 2 * i + 2. - moskalenco_a
  • I did not really get into the code. I obviously did not see this. I'll try to test it. You can do this, for example on heapSort. Those. remove the item from the pyramid, restore it. Then sort the remaining items. You need to do this many times on random data. - hedgehogues