堆化算法详解：最大堆和最小堆的维护

堆化是一种用于维护最大堆或最小堆性质的操作。最大堆性质指的是任意节点的值都大于或等于其子节点的值，而最小堆性质指的是任意节点的值都小于或等于其子节点的值。\r\n\r\n堆化操作的目标是通过交换节点的位置，使得违反堆性质的节点重新满足堆性质。这个操作通常用于插入新元素或删除堆顶元素后的调整。\r\n\r\n堆化操作可以分为向下堆化和向上堆化两种情况：\r\n\r\n1. 向下堆化（下沉操作）：\r\n - 选择当前节点和其左右子节点中值最大（最大堆）或最小（最小堆）的节点作为目标节点。\r\n - 若目标节点的值大于（最大堆）或小于（最小堆）当前节点的值，则交换两个节点的位置，并继续向下堆化目标节点。\r\n\r\n2. 向上堆化（上浮操作）：\r\n - 选择当前节点和其父节点比较。\r\n - 若当前节点的值大于（最大堆）或小于（最小堆）父节点的值，则交换两个节点的位置，并继续向上堆化当前节点。\r\n\r\n伪代码示例（以最大堆为例）：\r\nHeapifyDown(heap, index):\r\n largest = index\r\n left = 2 * index + 1\r\n right = 2 * index + 2\r\n \r\n if left < heap.length and heap[left] > heap[largest]:\r\n largest = left\r\n \r\n if right < heap.length and heap[right] > heap[largest]:\r\n largest = right\r\n \r\n if largest != index:\r\n swap(heap[index], heap[largest])\r\n HeapifyDown(heap, largest)\r\n\r\nHeapifyUp(heap, index):\r\n parent = (index - 1) / 2\r\n \r\n if parent >= 0 and heap[parent] < heap[index]:\r\n swap(heap[parent], heap[index])\r\n HeapifyUp(heap, parent)\r\n\r\n\r\n这样，通过不断地调用堆化操作，可以保持堆的性质。