设计与分析插入法

要在堆中插入元素，新元素最初会作为数组的最后一个元素附加到堆的末尾。

插入该元素后，可能会违反堆属性，因此通过将添加的元素与其父元素进行比较并将添加的元素向上移动一个级别，与父元素交换位置来修复堆属性。这个过程称为向上渗透。

重复比较，直到父元素大于或等于渗透元素。

Algorithm: Max-Heap-Insert (numbers[], key) 
heapsize = heapsize + 1 
numbers[heapsize] = -∞ 
i = heapsize 
numbers[i] = key 
while i > 1 and numbers[Parent(numbers[], i)] < numbers[i] 
   exchange(numbers[i], numbers[Parent(numbers[], i)]) 
   i = Parent (numbers[], i)

分析

最初，一个元素被添加到数组的末尾。如果它违反了堆属性，则该元素将与其父元素交换。树的高度是log n。需要执行的最大log n次操作。

因此，该函数的复杂度为O(log n)。

例子

让我们考虑一个最大堆，如下所示，其中需要添加新元素 5。

最初，55 将添加到该数组的末尾。

插入后，它违反了堆属性。因此，该元素需要与其父元素交换。交换后，堆如下所示。

同样，该元素违反了堆的属性。因此，它与其父级交换。

现在，我们必须停下来。

例子

C C++ Java Python

#include <stdio.h>
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}
int parent(int i) {
    if (i == 0)
        return -1;
    else
        return (i - 1) / 2;
}
void maxHeapInsert(int arr[], int* heapSize, int key) {
    (*heapSize)++;
    int i = *heapSize;
    arr[i] = key;
    while (i > 1 && arr[parent(i)] < arr[i]) {
        swap(&arr[i], &arr[parent(i)]);
        i = parent(i);
    }
}
int main() {
    int arr[100] = { 50, 30, 40, 20, 15, 10 }; // Initial Max-Heap
    int heapSize = 5; // Current heap size
    // New element to be inserted
    int newElement = 5;
    // Insert the new element into the Max-Heap
    maxHeapInsert(arr, &heapSize, newElement);
    // Print the updated Max-Heap
    printf("Updated Max-Heap: ");
    for (int i = 0; i <= heapSize; i++)
        printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

输出

Updated Max-Heap: 50 30 40 20 15 10 5

#include <iostream>
#include <vector>
using namespace std;
void swap(int& a, int& b) {
    int temp = a;
    a = b;
    b = temp;
}
int parent(int i) {
    if (i == 0)
        return -1;
    else
        return (i - 1) / 2;
}
void maxHeapInsert(vector<int>& arr, int& heapSize, int key) {
    heapSize++;
    int i = heapSize;   
    // Resize the vector to accommodate the new element
    arr.push_back(0);
    arr[i] = key;
    while (i > 1 && arr[parent(i)] < arr[i]) {
        swap(arr[i], arr[parent(i)]);
        i = parent(i);
    }
}
int main() {
    vector<int> arr = { 50, 30, 40, 20, 15, 10 }; // Initial Max-Heap
    int heapSize = 5; // Current heap size
    // New element to be inserted
    int newElement = 5;
    // Insert the new element into the Max-Heap
    maxHeapInsert(arr, heapSize, newElement);
    // Print the updated Max-Heap
    cout << "Updated Max-Heap: ";
    for (int i = 0; i <= heapSize; i++)
        cout << arr[i] << " ";
    cout << endl;
    return 0;
}

输出

Updated Max-Heap: 50 30 40 20 15 10 5

import java.util.Arrays;
public class MaxHeap {
    public static void swap(int arr[], int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    public static int parent(int i) {
        if (i == 0)
            return -1;
        else
            return (i - 1) / 2;
    }
    public static void maxHeapInsert(int arr[], int heapSize, int key) {
        heapSize++;
        int i = heapSize - 1; // Adjust the index for array insertion
        arr[i] = key;
        while (i > 0 && arr[parent(i)] < arr[i]) {
            swap(arr, i, parent(i));
            i = parent(i);
        }
    }
    public static void main(String args[]) {
        int arr[] = { 50, 30, 40, 20, 15, 10 }; // Initial Max-Heap
        int heapSize = 5; // Current heap size
        // New element to be inserted
        int newElement = 5;
        // Insert the new element into the Max-Heap
        maxHeapInsert(arr, heapSize, newElement);
        // Print the updated Max-Heap
        System.out.print("Updated Max-Heap: ");
        for (int i = 0; i <= heapSize; i++)
            System.out.print(arr[i] + " ");
        System.out.println();
    }
}

输出

Updated Max-Heap: 50 30 40 20 15 5

def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]
def parent(i):
    if i == 0:
        return -1
    else:
        return (i - 1) // 2
def max_heap_insert(arr, heap_size, key):
    heap_size += 1
    i = heap_size
    arr.append(key)
    while i > 0 and arr[parent(i)] < arr[i]:
        swap(arr, i, parent(i))
        i = parent(i)
if __name__ == "__main__":
    arr = [50, 30, 40, 20, 15, 10] # Initial Max-Heap
    heap_size = 5 # Current heap size
    # New element to be inserted
    new_element = 5
    # Insert the new element into the Max-Heap
    max_heap_insert(arr, heap_size, new_element)
    # Print the updated Max-Heap
    print("Updated Max-Heap:", arr)

输出

Updated Max-Heap: [50, 30, 40, 20, 15, 10, 5]