[C] Heap
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: $$O(nlogn)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\n/*\n * 1801. Number of Orders in the Backlog\n *\n * You are given a 2D integer array orders, where each orders[i] = \n * [pricei, amounti, orderTypei] denotes that amounti orders have \n * been placed of type orderTypei at the price pricei. \n * The orderTypei is:\n *\n * 0 if it is a batch of buy orders, or\n * 1 if it is a batch of sell orders.\n * Note that orders[i] represents a batch of amounti independent orders \n * with the same price and order type. All orders represented by orders[i] \n * will be placed before all orders represented by orders[i+1] for all \n * valid i.\n *\n * There is a backlog that consists of orders that have not been executed. \n * The backlog is initially empty. When an order is placed, the following happens:\n * \n * If the order is a buy order, you look at the sell order with the smallest \n * price in the backlog. If that sell order\'s price is smaller than or equal \n * to the current buy order\'s price, they will match and be executed, and that \n * sell order will be removed from the backlog. Else, the buy order is added \n * to the backlog.\n * Vice versa, if the order is a sell order, you look at the buy order with \n * the largest price in the backlog. If that buy order\'s price is larger than \n * or equal to the current sell order\'s price, they will match and be executed, \n * and that buy order will be removed from the backlog. Else, the sell order \n * is added to the backlog.\n * Return the total amount of orders in the backlog after placing all the orders \n * from the input. Since this number can be large, return it modulo 10^9 + 7.\n *\n * 1 <= orders.length <= 10^5\n * orders[i].length == 3\n * 1 <= pricei, amounti <= 10^9\n * orderTypei is either 0 or 1.\n */\n\ntypedef struct item {\n    int price;\n    unsigned int amount;\n} item_t;\n\n#define HEAP_SIZE 100000\n\nitem_t max_heap[HEAP_SIZE];\nint max_idx;\n\nitem_t min_heap[HEAP_SIZE];\nint min_idx;\n\nvoid max_init()\n{\n    max_idx = -1;\n}\n\nint max_push(item_t *item)\n{\n    if (max_idx + 1 == HEAP_SIZE) {\n        return -1;\n    }\n\n    max_idx++;\n    max_heap[max_idx] = *item;\n\n    for (int i = max_idx; i > 0; ) {\n        int parent = (i - 1) / 2;\n\n        if (max_heap[i].price > max_heap[parent].price) {\n            item_t tmp = max_heap[i];\n            max_heap[i] = max_heap[parent];\n            max_heap[parent] = tmp;\n        }\n\n        i = parent;\n    }\n\n    return 0;\n}\n\nint max_pop(item_t *item)\n{\n    if (max_idx == -1) {\n        return -1;\n    }\n\n    *item = max_heap[0];\n    max_heap[0] = max_heap[max_idx];\n    max_idx--;\n\n    for (int i = 1; i <= max_idx; ) {\n\n        int parent = (i - 1) / 2;\n\n        if (i + 1 <= max_idx && max_heap[i + 1].price > max_heap[i].price) {\n            i = i + 1;\n        }\n\n        if (max_heap[i].price > max_heap[parent].price) {\n            item_t tmp = max_heap[i];\n            max_heap[i] = max_heap[parent];\n            max_heap[parent] = tmp;\n        }\n\n        i = i * 2 + 1;\n\n    }\n\n    return 0;\n}\n\nvoid min_init()\n{\n    min_idx = -1;\n}\n\nint min_push(item_t *item)\n{\n    if (min_idx + 1 == HEAP_SIZE) {\n        return -1;\n    }\n\n    min_idx++;\n    min_heap[min_idx] = *item;\n\n    for (int i = min_idx; i > 0; ) {\n        int parent = (i - 1) / 2;\n\n        if (min_heap[i].price < min_heap[parent].price) {\n            item_t tmp = min_heap[i];\n            min_heap[i] = min_heap[parent];\n            min_heap[parent] = tmp;\n        }\n\n        i = parent;\n    }\n\n    return 0;\n}\n\nint min_pop(item_t *item)\n{\n    if (min_idx == -1) {\n        return -1;\n    }\n\n    *item = min_heap[0];\n    min_heap[0] = min_heap[min_idx];\n    min_idx--;\n\n    for (int i = 1; i <= min_idx; ) {\n\n        int parent = (i - 1) / 2;\n\n        if (i + 1 <= min_idx && min_heap[i + 1].price < min_heap[i].price) {\n            i = i + 1;\n        }\n\n        if (min_heap[i].price < min_heap[parent].price) {\n            item_t tmp = min_heap[i];\n            min_heap[i] = min_heap[parent];\n            min_heap[parent] = tmp;\n        }\n\n        i = i * 2 + 1;\n\n    }\n\n    return 0;\n}\n\nint getNumberOfBacklogOrders(int** orders, int ordersSize, int* ordersColSize){\n\n    /*\n     * Input:\n     *  **orders\n     *  ordersSize\n     *  *ordersColSize\n     */\n\n    item_t item;\n    int ans = 0;\n\n    max_init();\n    min_init();\n\n    for (int i = 0; i < ordersSize; i++) {\n        /* Buy */\n        if (orders[i][2] == 0) {\n            /* Search sell backlog and find out the lowest price */\n            for (; orders[i][1] && min_pop(&item) == 0; ) {\n\n                if (item.price <= orders[i][0]) {\n                    if (item.amount <= orders[i][1]) {\n                        orders[i][1] -= item.amount;\n                    }\n                    else {\n                        item.amount -= orders[i][1];\n                        orders[i][1] = 0;\n                        min_push(&item);\n                    }\n                }\n                else {\n                    min_push(&item);\n                    break;\n                }\n            }\n\n            /* Put the remain order to max heap */\n            if (orders[i][1] != 0) {\n                item.price = orders[i][0];\n                item.amount = orders[i][1];\n                max_push(&item);\n            }\n        }\n        /* Sell */\n        else if (orders[i][2] == 1) {\n            /* Search sell backlog and find out the lowest price */\n            for (; orders[i][1] && max_pop(&item) == 0; ) {\n\n                if (item.price >= orders[i][0]) {\n                    if (item.amount <= orders[i][1]) {\n                        orders[i][1] -= item.amount;\n                    }\n                    else {\n                        item.amount -= orders[i][1];\n                        orders[i][1] = 0;\n                        max_push(&item);\n                    }\n                }\n                else {\n                    max_push(&item);\n                    break;\n                }\n            }\n\n            /* Put the remain order to min heap */\n            if (orders[i][1] != 0) {\n                item.price = orders[i][0];\n                item.amount = orders[i][1];\n                min_push(&item);\n            }\n        }\n    }\n\n    while (max_pop(&item) == 0) {\n        ans += item.amount;\n        ans %= 1000000007;\n    }\n\n    while (min_pop(&item) == 0) {\n        ans += item.amount;\n        ans %= 1000000007;\n    }\n\n    /*\n     * Output:\n     *  Return the total amount of orders in the backlog after placing all the orders \n     *  from the input. Since this number can be large, return it modulo 10^9 + 7.\n     */\n\n    return ans;\n} \n```
['Array', 'C', 'Heap (Priority Queue)']