[Python] Concise Heap Implementation
Introduction\n\nWe need to find the total amount of orders that remain un-executed in the backlog of orders after a series of buy and sell orders have passed. A
### Introduction\n\nWe need to find the total amount of orders that remain un-executed in the backlog of orders after a series of buy and sell orders have passed. A buy order is executed if there exists a sell order in the backlog that has a selling price lower than or equal to the buying price, and a sell order is executed if there exists a buy order in the backlog that has a buying price greater than or equal to the selling price. Each time a buy/sell order comes, we need to compare its price with the sell/buy order with the smallest/greatest price, respectively.\n\nSince we need to obtain the smallest/greatest prices per order, a heap (priority queue) data structure is ideal for this task. For the buy order log, we require a max heap to obtain the greatest buying price; for the sell order log, we require a min heap to obtain the smallest buying price. Note that Python\'s `heapq` library implements a min heap, hence, to maintain a max heap, we need to **negate the buying prices**.\n\nTherefore, each time a buy/sell order with a given buying/selling price and the amount of orders is processed, we retrieve the sell/buy order with the smallest/largest price and execute the orders if the criteria (as mentioned above) is met. We continue to retrieve the sell/buy orders until;\n\n1. The criteria for executing the orders is no longer met.\n2. There are no more orders in the backlog to execute.\n3. There are no more orders in the current order to execute.\n\nAfter which, any remaining un-executed orders gets appended to its corresponding backlog.\n\n---\n\n### Base Implementation\n\nThis implementation features heavily on readability, and is meant to provide readers with a good understanding of how the code should work. If anything here is unclear or could be written better, please let me know in the comments.\n\n```python\nclass Solution:\n    def getNumberOfBacklogOrders(self, orders: List[List[int]]) -> int:\n        # note that: buy_log - max heap; sell_log - min heap\n        buy_log, sell_log = [], []\n        for price, amount, order_type in orders:\n            target_log = buy_log if order_type else sell_log\n            while amount and target_log:\n                # check that the appropriate buy/sell order fits the criteria\n                # if order type is sell, ensure buy order price >= current price\n                # else if order type is buy, ensure sell order price <= current price\n                if (order_type and abs(target_log[0][0]) < price) or \\\n                        (not order_type and target_log[0][0] > price):\n                    break\n                current_price, current_amount = heappop(target_log)\n                # cancel buy and sell orders\n                min_amount = min(amount, current_amount)\n                amount -= min_amount\n                current_amount -= min_amount\n                # check if there are remaining target orders\n                if current_amount:\n                    heappush(target_log, (current_price, current_amount))\n            # check if there are remaining current orders\n            if amount:\n                heappush(sell_log if order_type else buy_log,\n                         # negate price if order type is buy\n                         # so as to maintain a max heap for buy orders\n                         (price if order_type else -price, amount))\n        return (sum(log_amount for _, log_amount in buy_log) + \\\n                sum(log_amount for _, log_amount in sell_log))%int(1e9+7)\n```\n\n---\n\n### Concise Implementation\n\nInstead of having two separate heaps to manage the buy and sell logs, we can combine them into one tuple and use the order type to access the proper logs. If implemented correctly, taking the different comparison operators / min/max heap into account, we can save a lot of lines because none of the code is repeated.\n\nThe following code has been revised for readability, as suggested by [@daBozz](https://leetcode.com/daBozz/).\n\n```python\nclass Solution:\n    def getNumberOfBacklogOrders(self, orders: List[List[int]]) -> int:\n        backlog = ([], [])  # (buy (max-heap), sell (min-heap))\n        for price, amount, order_type in orders:\n            # check that the appropriate buy/sell order fits the criteria in the while loop\n            # note that le, ge come from the Python operator library\n            # equivalent to: le - lambda a, b: a <= b\n            #                ge - lambda a, b: a >= b\n            while amount > 0 and \\\n                    (target_log := backlog[1-order_type]) and \\\n                    (le, ge)[order_type](abs(target_log[0][0]), price):\n                curr_price, curr_amount = heappop(target_log)\n                if (amount := amount-curr_amount) < 0:  # there are remaining target orders\n                    heappush(target_log, (curr_price, -amount))\n            if amount > 0:  # there are remaining current orders\n                heappush(backlog[order_type], (price if order_type else -price, amount))\n        # note that itemgetter comes from the Python operator library\n        # equivalent to: lambda t: t[1]\n        return sum(sum(map(itemgetter(1), log)) for log in backlog)%int(1e9+7)\n```\n\n**TC: O(nlogk)**, where `n` is the number of orders and `k` is the maximum length of either the buy or sell backlogs.\n**SC: O(n)**, taking both backlogs into account.\n\n---\n\nPlease upvote if this has helped you! Appreciate any comments as well :)
['Heap (Priority Queue)', 'Python', 'Python3']