Inplement Priority Queue(heap) in C#

Data structure

Posted by Yiling on June 22, 2020

I will continue update this code during study C#, now it may looks not elegant enough.

Please tell me if anyone needs a Python3 version, I am good at Python.

public class heapq{
    List<int> h = new List<int>();
    public int lastidx = -1;
    public void heappush(int num){
        h.Add(num);
        lastidx ++;
        int parent = lastidx / 2;
        int curidx = lastidx;
        while(num > h[parent]){
        // switch if parent is smaller
            h[curidx] = h[parent];
            h[parent] = num;
            curidx = parent;
            parent = parent / 2;
        }
    }
    public int heappop(){
        int to_return = h[0];
        h[0] = h[lastidx];
        // O(1) according to MSDN https://docs.microsoft.com/en-us/dotnet/api/system.collections.generic.list-1.removeat?view=netcore-3.1
        h.RemoveAt(lastidx);
        lastidx --;
        if(lastidx < 1){
            return to_return;
        }
        if(lastidx == 1){
            h.Sort((x, y) => -x.CompareTo(y));
            return to_return;
        }
        // if len(list) > 2
        shift_down(0);
        return to_return;
    }
    public void shift_down(int parent){
        int left_child = 2 * parent + 1;
        int right_child = 2 * parent + 2;
        int curlargest = h[parent];
        if(right_child <= lastidx){
            if(h[left_child] > curlargest && h[left_child] > h[right_child]){
                h[parent] = h[left_child];
                h[left_child] = curlargest;
                shift_down(left_child);
            }
            else if(h[right_child] > curlargest && h[right_child] >= h[left_child]){
                h[parent] = h[right_child];
                h[right_child] = curlargest;
                shift_down(right_child);
            }
        }
        else if(left_child == lastidx){
            if(h[left_child] > curlargest){
                h[parent] = h[left_child];
                h[left_child] = curlargest;
            }
        }
    }
}