[Python] O(log n) time for both seat() and leave() with a customized heap implementation
This solution is similar to https://leetcode.com/problems/exam-room/discuss/139941/Python-O(log-n)-time-for-both-seat()-and-leave()-with-heapq-and-dicts-Detaile
This solution is similar to https://leetcode.com/problems/exam-room/discuss/139941/Python-O(log-n)-time-for-both-seat()-and-leave()-with-heapq-and-dicts-Detailed-explanation/147981. Many thanks to [@spatar](https://leetcode.com/spatar). \n\nThe main difference is that we will delete the segments from the heap when they become invalid due to the leave. Since the customized implementation of heap is not as optimized as heapq, the running time of this solution (116ms) is longer than the original heapq solution (72ms).\n\n```\nclass IndexedHeap:\n    """This is a simple implementation of a min/max-heap.\n    Note that we assume that each item of the heap is a list\n    where its last element indicates the index of the item\n    in the heap.\n    """\n    def __init__(self, reverse=False):\n        # By default this heap is a min-heap. But if the flag \n        # reverse is True, it will be a max-heap.\n        self._reverse = reverse\n        \n        \n    def _lt(self, x, y):\n        if not self._reverse:\n            return x < y\n        else:\n            return x > y\n            \n         \n    def _le(self, x, y):\n        if not self._reverse:\n            return x <= y\n        else:\n            return x >= y\n                 \n    \n    def _percolate_up(self, heap):\n        """Percolate the last item up to the appropriate \n        position of the heap.\n        """\n        curr_index = len(heap) - 1\n        while curr_index > 0:\n            parent_index = (curr_index - 1) // 2\n            if self._le(heap[parent_index], heap[curr_index]):\n                break\n            else:\n                tmp = heap[parent_index]\n                heap[parent_index] = heap[curr_index]\n                heap[curr_index] = tmp        \n                # Swap back the indexes of the elements in the heap.\n                heap[parent_index][-1] = parent_index\n                heap[curr_index][-1] = curr_index\n                \n                curr_index = parent_index\n                \n    \n    def _get_min_child(self, heap, item_index):\n        """Get the index of the minimum child of an item.\n        If the item doesn\'t have any child, we will return -1.\n        """\n        left_child = 2*item_index + 1\n        if left_child > len(heap) - 1:\n            return -1\n        \n        ret_index = left_child\n        right_child = 2*item_index + 2\n        if right_child < len(heap) and self._lt(heap[right_child], heap[left_child]):\n            ret_index = right_child\n            \n        return ret_index\n   \n        \n    def _percolate_down(self, heap, item_index):\n        """Percolate the element at item_index down to the appropriate \n        position of the heap.\n        """\n        curr_index = item_index\n        min_child_index = self._get_min_child(heap, curr_index)\n        while min_child_index != -1:\n            if self._lt(heap[curr_index], heap[min_child_index]):\n                break\n            else:\n                tmp = heap[min_child_index]\n                heap[min_child_index] = heap[curr_index]\n                heap[curr_index] = tmp\n                # Swap back the indexes of the elements in the heap.\n                heap[min_child_index][-1] = min_child_index\n                heap[curr_index][-1] = curr_index\n                \n                curr_index = min_child_index\n                min_child_index = self._get_min_child(heap, curr_index)\n   \n        \n    def heaplify(self, heap_to_be):\n        """Create a heap in-place from a list."""\n        # Initialize the indexes of the elements in the heap.\n        for index in range(len(heap_to_be)):\n            heap_to_be[index][-1] = index \n        \n        curr_index = len(heap_to_be) // 2 - 1\n        while curr_index >= 0:\n            self._percolate_down(heap_to_be, curr_index)\n            curr_index -= 1\n        \n        \n    def heappush(self, heap, item):\n        """Push one item into the heap."""\n        item[-1] = len(heap)\n        heap.append(item)\n        # Percolate up the item from the end of the heap.\n        self._percolate_up(heap)\n        \n        \n    def heappop(self, heap):\n        """Pop the root (i.e., the minimum/maximum item) out of the heap."""\n        if not heap:\n            raise IndexError(\'empty heap\')\n        \n        ret = heap[0]\n        heap[0] = heap[-1]\n        # Reset the index of the root.\n        heap[0][-1] = 0\n        heap.pop()\n        \n        self._percolate_down(heap, 0)\n        \n        return ret\n        \n        \n    def heapdelete(self, heap, item_index):\n        """Delete the item at item_index from the heap."""\n        if item_index < 0 or item_index >= len(heap):\n            return\n        \n        # Move the last item to item_index.\n        heap[item_index] = heap[-1]\n        # Reset the index of the item at item_index.\n        heap[item_index][-1] = item_index\n        # Remove the last item from the heap.\n        heap.pop()\n        \n        self._percolate_down(heap, item_index)\n        \n        return\n\n\nclass ExamRoom(object):\n    def __init__(self, N):\n        """\n        :type N: int\n        """\n        self.N = N\n        # This max-heap keeps a list of empty segments where the segments\n        # are compared firstly with their lengths and then with its start indice\n        # if their lengths are the same.\n        self.heap = []\n        # A dict from the segment start index to the segment\n        self.avail_first = {}\n        # A dict from the segment end index to the segment\n        self.avail_last = {}\n        # Create the min-heap helper.\n        self.min_h = IndexedHeap()\n        # Initially we have one big empty segment [0, N - 1].\n        self.put_segment(0, self.N - 1)\n        \n\n    def put_segment(self, first, last):\n        # Calculate the priority of the segment where the priority is the maximum \n        # closest distance if the new student sits at one seat in the segment.\n        if first == 0 or last == self.N - 1:\n            # If the empty segment includes either 0 or N - 1\n            priority = last - first\n        else:\n            priority = (last - first) // 2\n\n        # segment[0] = priority;\n        # segment[1] = the starting seat of the segment\n        # segment[2] = the ending seat of the segment\n        # segment[3] = the index of this segment in the heap.\n        # Note that:\n        # (1) Take the negative of priority because we want to use a min-heap.\n        # (2) The segment index will be set in IndexedHeap.heappush().\n        segment = [-priority, first, last, -1]\n\n        self.avail_first[first] = segment\n        self.avail_last[last] = segment\n\n        self.min_h.heappush(self.heap, segment)\n\n    def seat(self):\n        """\n        :rtype: int\n        """\n        # Get the segment with the maximum length.\n        _, first, last, _ = self.min_h.heappop(self.heap)\n        self.avail_first.pop(first)\n        self.avail_last.pop(last)\n\n        if first == 0:\n            # Seat the student at 0.\n            ret = 0\n            if first != last:\n                self.put_segment(first + 1, last)\n        elif last == self.N - 1:\n            # Seat the student at N - 1.\n            ret = last\n            if first != last:\n                self.put_segment(first, last - 1)\n        else:\n            # Seat the student in the middle of the segment.\n            ret = first + (last - first) // 2\n            \n            if ret > first:\n                self.put_segment(first, ret - 1)\n            if ret < last:\n                self.put_segment(ret + 1, last)\n\n        return ret\n\n    def leave(self, p):\n        """\n        :type p: int\n        :rtype: void\n        """\n        # Removing p at least leads to a hole at p.\n        first = p\n        last = p\n\n        # Check if we need to delete the left and right segments \n        # neighboring p.\n        left = p - 1\n        right = p + 1\n\n        if left >= 0 and left in self.avail_last:\n            # Delete the left segment if it exists. Note that we don\'t \n            # delete the segment from the map self.avail_first since \n            # its value will be overwritten in self.put_segment().\n            segment_left = self.avail_last.pop(left)\n            first = segment_left[1]\n            # Instead of marking the segment as invalid, we delete \n            # the segment from the heap.\n            self.min_h.heapdelete(self.heap, segment_left[3])\n            \n        if right < self.N and right in self.avail_first:\n            # Delete the right segment if it exists. Note that we don\'t \n            # delete the segment from the map self.avail_last since \n            # its value will be overwritten in self.put_segment(). \n            segment_right = self.avail_first.pop(right)\n            last = segment_right[2]\n            # Instead of marking the segment as invalid, we delete \n            # the segment from the heap.\n            self.min_h.heapdelete(self.heap, segment_right[3])\n\n        # Push the new segment into the heap.\n        self.put_segment(first, last)\n```
[]