7 堆 6题

sy365: 向下调整构建大顶堆

https://sunnywhy.com/sfbj/9/7/365

现有个不同的正整数，将它们按层序生成完全二叉树，然后使用向下调整的方式构建一个完整的大顶堆。最后按层序输出堆中的所有元素。

输入

第一行一个整数$n(1\le n\le {10}^3)$，表示正整数的个数；

第二行 n 个整数$a_i (1 \le a_i \le 10^4) $​，表示正整数序列。

输出

输出 n 个整数，表示堆的层序序列，中间用空格隔开，行末不允许有多余的空格。

样例1

输入

6
3 2 6 5 8 7

输出

8 5 7 3 2 6

解释

调整前的完全二叉树和调整后的堆如下图所示。

解法1:

class BinaryHeap:
    def __init__(self):
        self._heap = []

    def _perc_up(self, i):
        while (i - 1) // 2 >= 0:
            parent_idx = (i - 1) // 2
            if self._heap[i] < self._heap[parent_idx]:
                self._heap[i], self._heap[parent_idx] = (
                    self._heap[parent_idx],
                    self._heap[i],
                )
            i = parent_idx

    def insert(self, item):
        self._heap.append(item)
        self._perc_up(len(self._heap) - 1)

    def _perc_down(self, i):
        while 2 * i + 1 < len(self._heap):
            sm_child = self._get_min_child(i)
            if self._heap[i] > self._heap[sm_child]:
                self._heap[i], self._heap[sm_child] = (
                    self._heap[sm_child],
                    self._heap[i],
                )
            else:
                break
            i = sm_child

    def _get_min_child(self, i):
        if 2 * i + 2 > len(self._heap) - 1:
            return 2 * i + 1
        if self._heap[2 * i + 1] < self._heap[2 * i + 2]:
            return 2 * i + 1
        return 2 * i + 2

    def delete(self):
        self._heap[0], self._heap[-1] = self._heap[-1], self._heap[0]
        result = self._heap.pop()
        self._perc_down(0)
        return result

    def heapify(self, not_a_heap):
        self._heap = not_a_heap[:]
        i = len(self._heap) // 2 - 1    # 超过中点的节点都是叶子节点
        while i >= 0:
            #print(f'i = {i}, {self._heap}')
            self._perc_down(i)
            i = i - 1



n = int(input().strip())
heap = list(map(int, input().strip().split())) # [9, 5, 6, 2, 3]
heap = [-x for x in heap]

bh = BinaryHeap()
bh.heapify(heap)
ans = [-x for x in bh._heap]
print(*ans)

解法2:

To solve this problem, you can use the concept of a binary heap. A binary heap is a complete binary tree where each node is either greater than or equal to its children (in a max heap) or less than or equal to its children (in a min heap). In this case, you are asked to create a max heap.

Here is a step-by-step plan:

1. Initialize an array heap of size n to store the elements of the heap.
2. For each element in the input, insert it into the heap array.
3. For each non-leaf node in the heap array (starting from the last non-leaf node and moving to the root), perform a downward adjustment to ensure the max heap property is maintained.
4. Print the elements of the heap array in order.

Here is the Python code that implements this plan:

def down_adjust(parent_index, length):
    temp = heap[parent_index]
    child_index = 2 * parent_index + 1
    while child_index < length:
        if child_index + 1 < length and heap[child_index + 1] > heap[child_index]:
            child_index += 1
        if temp > heap[child_index]:
            break
        heap[parent_index] = heap[child_index]
        parent_index = child_index
        child_index = 2 * child_index + 1
    heap[parent_index] = temp

n = int(input().strip())
heap = list(map(int, input().strip().split()))

for i in range((n - 2) // 2, -1, -1):
    down_adjust(i, n)

print(' '.join(map(str, heap)))

This code reads the number of elements and the elements themselves from the input, inserts each element into the heap array, performs a downward adjustment for each non-leaf node in the heap array to ensure the max heap property is maintained, and then prints the elements of the heap array in order.

sy366: 向上调整构建大顶堆

https://sunnywhy.com/sfbj/9/7/366

现有 n 个不同的正整数，将它们按层序生成完全二叉树，然后使用向上调整的方式构建一个完整的大顶堆。最后按层序输出堆中的所有元素。

输入

第一行一个整数 $n(1\le n\le {10}^3)$，表示正整数的个数；

第二行 n 个整数$a_i (1 \le a_i \le 10^4) $​，表示正整数序列。

输出

输出 n 个整数，表示堆的层序序列，中间用空格隔开，行末不允许有多余的空格。

样例1

输入

6
3 2 6 5 8 7

输出

8 6 7 2 5 3

解释

调整前的完全二叉树和调整后的堆如下图所示。

To solve this problem, you can use the concept of a binary heap. A binary heap is a complete binary tree where each node is either greater than or equal to its children (in a max heap) or less than or equal to its children (in a min heap). In this case, you are asked to create a max heap.

Here is a step-by-step plan:

1. Initialize an array heap of size n to store the elements of the heap.
2. For each element in the input, insert it into the heap array.
3. For each inserted node in the heap array (starting from the last inserted node and moving to the root), perform an upward adjustment to ensure the max heap property is maintained.
4. Print the elements of the heap array in order.

Here is the Python code that implements this plan:

def up_adjust(child_index):
    temp = heap[child_index]
    parent_index = (child_index - 1) // 2
    while child_index > 0 and temp > heap[parent_index]:
        heap[child_index] = heap[parent_index]
        child_index = parent_index
        parent_index = (parent_index - 1) // 2
    heap[child_index] = temp

n = int(input().strip())
heap = list(map(int, input().strip().split()))

for i in range(1, n):
    up_adjust(i)

print(' '.join(map(str, heap)))

This code reads the number of elements and the elements themselves from the input, inserts each element into the heap array, performs an upward adjustment for each inserted node in the heap array to ensure the max heap property is maintained, and then prints the elements of the heap array in order.

sy367: 删除堆顶元素

https://sunnywhy.com/sfbj/9/7/367

现有 n 个不同的正整数，将它们按层序生成完全二叉树，然后使用向下调整的方式构建一个完整的大顶堆。然后删除堆顶元素，并将层序最后一个元素置于堆顶，进行一次向下调整，以形成新的堆。最后按层序输出新堆中的所有元素。

输入

第一行一个整数 $n(1\le n\le {10}^3)$，表示正整数的个数；

第二行 n 个整数 $a_i (1 \le a_i \le 10^4) $​，表示正整数序列。

输出

输出 n - 1 个整数，表示堆的层序序列，中间用空格隔开，行末不允许有多余的空格。

样例1

输入

6
3 2 6 5 8 7

输出

7 5 6 3 2

解释

操作过程如下图所示。

解法1:

class BinHeap:
    def __init__(self):
        self.heapList = [0]
        self.currentSize = 0

    def percUp(self, i):
        while i // 2 > 0:
            if self.heapList[i] < self.heapList[i // 2]:
                tmp = self.heapList[i // 2]
                self.heapList[i // 2] = self.heapList[i]
                self.heapList[i] = tmp
            i = i // 2

    def insert(self, k):
        self.heapList.append(k)
        self.currentSize = self.currentSize + 1
        self.percUp(self.currentSize)

    def percDown(self, i):
        while (i * 2) <= self.currentSize:
            mc = self.minChild(i)
            if self.heapList[i] > self.heapList[mc]:
                tmp = self.heapList[i]
                self.heapList[i] = self.heapList[mc]
                self.heapList[mc] = tmp
            i = mc

    def minChild(self, i):
        if i * 2 + 1 > self.currentSize:
            return i * 2
        else:
            if self.heapList[i * 2] < self.heapList[i * 2 + 1]:
                return i * 2
            else:
                return i * 2 + 1

    def delMin(self):
        retval = self.heapList[1]
        self.heapList[1] = self.heapList[self.currentSize]
        self.currentSize = self.currentSize - 1
        self.heapList.pop()
        self.percDown(1)
        return retval

    def buildHeap(self, alist):
        i = len(alist) // 2
        self.currentSize = len(alist)
        self.heapList = [0] + alist[:]
        while (i > 0):
            #print(f'i = {i}, {self.heapList}')
            self.percDown(i)
            i = i - 1
        #print(f'i = {i}, {self.heapList}')


n = int(input().strip())
heap = list(map(int, input().strip().split())) # [9, 5, 6, 2, 3]
heap = [-x for x in heap]

bh = BinHeap()
bh.buildHeap(heap)

bh.delMin()

ans = [-x for x in bh.heapList[1:]]
print(*ans)

解法2:

To solve this problem, you can use the concept of a binary heap. A binary heap is a complete binary tree where each node is either greater than or equal to its children (in a max heap) or less than or equal to its children (in a min heap). In this case, you are asked to create a max heap, delete the root, and then adjust the heap.

Here is a step-by-step plan:

1. Initialize an array heap of size n to store the elements of the heap.
2. For each element in the input, insert it into the heap array.
3. For each non-leaf node in the heap array (starting from the last non-leaf node and moving to the root), perform a downward adjustment to ensure the max heap property is maintained.
4. Delete the root of the heap and replace it with the last element in the heap.
5. Perform a downward adjustment on the new root to maintain the max heap property.
6. Print the elements of the heap array in order.

Here is the Python code that implements this plan:

def down_adjust(parent_index, length):
    temp = heap[parent_index]
    child_index = 2 * parent_index + 1
    while child_index < length:
        if child_index + 1 < length and heap[child_index + 1] > heap[child_index]:
            child_index += 1
        if temp > heap[child_index]:
            break
        heap[parent_index] = heap[child_index]
        parent_index = child_index
        child_index = 2 * child_index + 1
    heap[parent_index] = temp

n = int(input().strip())
heap = list(map(int, input().strip().split()))

for i in range((n - 2) // 2, -1, -1):
    down_adjust(i, n)

heap[0] = heap[n - 1]
down_adjust(0, n - 1)

print(' '.join(map(str, heap[:-1])))

This code reads the number of elements and the elements themselves from the input, inserts each element into the heap array, performs a downward adjustment for each non-leaf node in the heap array to ensure the max heap property is maintained, deletes the root of the heap and replaces it with the last element in the heap, performs a downward adjustment on the new root to maintain the max heap property, and then prints the elements of the heap array in order.

sy368: 堆排序

https://sunnywhy.com/sfbj/9/7/368

输入 n 个正整数，使用堆排序算法将它们按从小到大的顺序进行排序。

输入

第一行一个整数 $n(1\le n\le 50)$，表示正整数的个数；

第二行为用空格隔开的 n 个正整数（每个正整数均不超过100）。

输出

输出一行，表示排序后的 n 个正整数。整数间用一个空格隔开，行末不允许有多余的空格。

样例1

输入

5
2 8 5 1 3

输出

1 2 3 5 8

解释

从小到大排序后可以得到序列1 2 3 5 8

解法1:

class BinHeap:
    def __init__(self):
        self.heapList = [0]
        self.currentSize = 0

    def percUp(self, i):
        while i // 2 > 0:
            if self.heapList[i] < self.heapList[i // 2]:
                tmp = self.heapList[i // 2]
                self.heapList[i // 2] = self.heapList[i]
                self.heapList[i] = tmp
            i = i // 2

    def insert(self, k):
        self.heapList.append(k)
        self.currentSize = self.currentSize + 1
        self.percUp(self.currentSize)

    def percDown(self, i):
        while (i * 2) <= self.currentSize:
            mc = self.minChild(i)
            if self.heapList[i] > self.heapList[mc]:
                tmp = self.heapList[i]
                self.heapList[i] = self.heapList[mc]
                self.heapList[mc] = tmp
            i = mc

    def minChild(self, i):
        if i * 2 + 1 > self.currentSize:
            return i * 2
        else:
            if self.heapList[i * 2] < self.heapList[i * 2 + 1]:
                return i * 2
            else:
                return i * 2 + 1

    def delMin(self):
        retval = self.heapList[1]
        self.heapList[1] = self.heapList[self.currentSize]
        self.currentSize = self.currentSize - 1
        self.heapList.pop()
        self.percDown(1)
        return retval

    def buildHeap(self, alist):
        i = len(alist) // 2
        self.currentSize = len(alist)
        self.heapList = [0] + alist[:]
        while (i > 0):
            #print(f'i = {i}, {self.heapList}')
            self.percDown(i)
            i = i - 1
        #print(f'i = {i}, {self.heapList}')


n = int(input().strip())
heap = list(map(int, input().strip().split())) # [9, 5, 6, 2, 3]

bh = BinHeap()
bh.buildHeap(heap)

ans = []
while bh.currentSize > 0:
    ans.append(bh.delMin())
print(*ans)

解法2:

To solve this problem, you can use the heap sort algorithm. Heap sort is a comparison-based sorting algorithm that uses a binary heap data structure. It works by building a max heap from the input data, then iteratively removing the maximum element from the heap and inserting it at the end of the sorted section of the array.

Here is a step-by-step plan:

1. Initialize an array heap of size n to store the elements of the heap.
2. For each element in the input, insert it into the heap array.
3. For each non-leaf node in the heap array (starting from the last non-leaf node and moving to the root), perform a downward adjustment to ensure the max heap property is maintained.
4. Repeatedly swap the first element in the heap with the last element in the unsorted section of the array, then perform a downward adjustment on the new root to maintain the max heap property.
5. Print the elements of the heap array in order.

Here is the Python code that implements this plan:

def down_adjust(parent_index, length):
    temp = heap[parent_index]
    child_index = 2 * parent_index + 1
    while child_index < length:
        if child_index + 1 < length and heap[child_index + 1] > heap[child_index]:
            child_index += 1
        if temp > heap[child_index]:
            break
        heap[parent_index] = heap[child_index]
        parent_index = child_index
        child_index = 2 * child_index + 1
    heap[parent_index] = temp

n = int(input().strip())
heap = list(map(int, input().strip().split()))

for i in range((n - 2) // 2, -1, -1):
    down_adjust(i, n)

for i in range(n - 1, 0, -1):
    heap[i], heap[0] = heap[0], heap[i]
    down_adjust(0, i)

print(' '.join(map(str, heap)))

This code reads the number of elements and the elements themselves from the input, inserts each element into the heap array, performs a downward adjustment for each non-leaf node in the heap array to ensure the max heap property is maintained, repeatedly swaps the first element in the heap with the last element in the unsorted section of the array and performs a downward adjustment on the new root, and then prints the elements of the heap array in order.

sy369: 数据流第K大元素

https://sunnywhy.com/sfbj/9/7/369

现有一个初始为空的序列 S，对其执行 n 个操作，每个操作是以下两种操作之一：

1. 往序列 S 中加入一个正整数；
2. 输出当前序列 S 中第大的数。

其中，第大是指将序列从大到小排序后的第 k 个数。

输入

第一行两个整数$n、k(1\le n\le {10}^4,2\le k\le 100)$，分别表示操作个数、需要输出第几大的数；

接下来 n 行，每行一个操作信息：使用"Push x"来表示往序列中加入正整数 $x(1\le x\le {10}^9)$，使用"Print"来表示需要输出当前序列中第大的数。

输出

每次执行Print操作时，输出一行，表示当前序列中第大的数。如果不存在第大的数，那么输出-1。

样例1

输入

7 2
Push 1
Print
Push 3
Print
Push 7
Push 6
Print

输出

-1
1
6

解释

第一个Print时序列中元素为1，不存在第2大的元素，因此输出-1；

第二个Print时序列中元素为1 3，因此第2大的元素为1；

第三个Print时序列中元素为1 3 7 6，因此第2大的元素为6。

To solve this problem, you can use a priority queue data structure. A priority queue can efficiently insert elements and retrieve the maximum element. In Python, you can use the heapq module to implement a priority queue. However, Python's heapq module only provides a min-heap, so you need to insert the negative of the numbers to simulate a max-heap.

Here is a step-by-step plan:

1. Initialize an empty list heap to store the elements of the heap.
2. For each operation:
   • If the operation is "Push x", insert -x into the heap.
   • If the operation is "Print", if the size of the heap is less than k, print -1. Otherwise, create a copy of the heap, pop k elements from the copy, and print the negative of the last popped element.

Here is the Python code that implements this plan:

import heapq

n, k = map(int, input().split())
heap = []

for _ in range(n):
    operation = input().split()
    if operation[0] == "Push":
        heapq.heappush(heap, -int(operation[1]))
    else:  # operation[0] == "Print"
        if len(heap) < k:
            print(-1)
        else:
            temp_heap = heap.copy()
            for _ in range(k):
                result = heapq.heappop(temp_heap)
            print(-result)

This code reads the number of operations and the value of k from the input, then for each operation, if the operation is "Push x", it inserts -x into the heap, and if the operation is "Print", it checks if the size of the heap is less than k, if so, it prints -1, otherwise, it creates a copy of the heap, pops k elements from the copy, and prints the negative of the last popped element.

sy370: 数据流中位数

https://sunnywhy.com/sfbj/9/7/370

现有一个初始为空的序列 S，对其执行 n 个操作，每个操作是以下两种操作之一：

1. 往序列 S 中加入一个正整数 x ；
2. 输出当前序列 S 的中位数。

注：序列的中位数是指，将这个序列从小到大排序后最中间的那个元素；如果最中间有两个元素，那么取这两个元素的平均数作为序列的中位数。

输入

第一行一个整数 $n(2\le n\le {10}^4)$，表示操作个数；

接下来行，每行一个操作信息：使用"Push x"来表示往序列中加入正整数$x(1\le x\le {10}^5)$，使用"Print"来表示需要输出当前序列的中位数。

数据保证不会在序列为空时进行Print操作。

输出

每次执行Print操作时，输出一行，表示当前序列的中位数。结果保留一位小数。

样例1

输入

6
Push 3
Push 7
Push 6
Print
Push 1
Print

输出

6.0
4.5

解释

第一个Print时序列中元素为3 7 6，因此中位数是6；

第二个Print时序列中元素为3 7 6 1，因此中位数是。

To solve this problem, you can use two heaps: a max heap to store the smaller half of the numbers, and a min heap to store the larger half. The median is then either the maximum element in the max heap (when the total number of elements is odd) or the average of the maximum element in the max heap and the minimum element in the min heap (when the total number of elements is even).

Here is a step-by-step plan:

1. Initialize an empty max heap left and an empty min heap right.
2. For each operation:
   • If the operation is "Push x", insert x into the appropriate heap. If the size of the heaps differ by more than 1 after the insertion, balance the heaps by moving the top element from the heap with more elements to the heap with fewer elements.
   • If the operation is "Print", print the median. The median is the top element of left if the total number of elements is odd, or the average of the top elements of left and right if the total number of elements is even.

Here is the Python code that implements this plan:

import heapq

n = int(input().strip())
left, right = [], []

for _ in range(n):
    operation = input().split()
    if operation[0] == "Push":
        x = int(operation[1])
        if not left or x <= -left[0]:
            heapq.heappush(left, -x)
        else:
            heapq.heappush(right, x)
        if len(left) < len(right):
            heapq.heappush(left, -heapq.heappop(right))
        elif len(left) > len(right) + 1:
            heapq.heappush(right, -heapq.heappop(left))
    else:  # operation[0] == "Print"
        if len(left) > len(right):
            print(f"{-left[0]:.1f}")
        else:
            print(f"{(-left[0] + right[0]) / 2:.1f}")

This code reads the number of operations from the input, then for each operation, if the operation is "Push x", it inserts x into the appropriate heap and balances the heaps if necessary, and if the operation is "Print", it prints the median.