Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

0x00 Delete operation

int del( int heap[]) {
    int ele = heap[1];
    heap[1] = heap[heap[0]];
    heap[0]--;
    int i=1;
    int min;
    if( heap[2*i+1] > heap[2*i] ) {
        min = 2*i;
    } else {
        min = 2*i+1;
    }
    
    while(min<heap[0] && heap[i] > heap[min]) {
        swap(&heap[i],&heap[min]);
        i=min;
        if(heap[2*min+1] > heap[2*min]) {
            min = 2*min;
        } else {
            min = 2*min+1;
        }
    }
    return ele;
}
Copy the code

The idea is a little more complicated, but we delete nodes by removing the topmost node, then moving the last element to the vertex, and then adjusting the heap. Because we want to return the value of the deleted element, we define a ele to hold the deleted element and then overwrite it with the last element. Because one element is deleted, the number of elements in the heap is reduced by one, so the first element is reduced.

The index of the topmost node is 1. We first compare this element with the minimum value in the left and right child nodes. If it is greater than the minimum value, the coordinate of the minimum value is assigned to min.

The loop is then entered, and when the index of min does not exceed heap[0], which is the number of elements, and the value of the current node is greater than the minimum value of the left and right child nodes, their positions are swapped, and the coordinates of the original minimum value are assigned to the current node, and the left and right child nodes are minimised, and the size is compared.

0x01 Update operation

void update( int x, int pos, int heap[], int len ) { if(heap[pos] > x) { heap[pos] = x; int i = pos; while(heap[i]<heap[i/2]) { swap(&heap[i],&heap[i/2]); i/=2; } } if(heap[pos] < x) { heap[pos] = x; int i=pos; int min; if( heap[2*i+1] > heap[2*i] ) { min = 2*i; } else { min = 2*i+1; } while(min<heap[0] && heap[i] > heap[min]) { swap(&heap[i],&heap[min]); i=min; if(heap[2*min+1] > heap[2*min]) { min = 2*min; } else { min = 2*min+1; }}}}Copy the code

The update operation is a combination of the above two methods. If the updated value is less than the original value, the increment is the same as the increment operation.

If the updated value is greater than the original value, the drop operation is performed, which is the same as deleting the element.