最小堆的建立 插入 与删除

最小堆是一种特殊的二叉树结构，其中每个节点的值都小于或等于其子节点的值。最小堆通常用于实现优先队列等数据结构。下面介绍最小堆的建立、插入和删除操作。

1. 最小堆的建立

最小堆可以通过插入元素来逐步建立。首先将第一个元素插入堆中，然后依次将剩余的元素插入堆中。每次插入一个新元素时，将其放在堆的最后一个位置，然后将其与其父节点进行比较，如果其值比父节点小，则交换两者的位置，直到其父节点的值小于等于它为止。重复这个过程，直到所有元素都被插入到堆中，这样就得到了一个最小堆。

2. 插入元素

向最小堆中插入一个新元素时，首先将其放在堆的最后一个位置，然后将其与其父节点进行比较，如果其值比父节点小，则交换两者的位置，直到其父节点的值小于等于它为止。这样就保证了插入新元素后仍然是一个最小堆。

3. 删除元素

从最小堆中删除一个元素时，首先将堆顶元素（即最小值）取出，并将堆的最后一个元素放到堆顶位置。然后将其与其子节点进行比较，如果其值比其中某个子节点的值大，则将其与该子节点交换位置，重复这个过程，直到其值小于等于其子节点的值为止。这样就保证了删除元素后仍然是一个最小堆。

相关问题

c语言堆的建立和维护

堆是一种特殊的树形数据结构，其中每个节点都有一个值，通常我们所说的堆都是指二叉堆，它满足以下两个性质：

1. 父节点的值总是大于或等于（小于或等于）任何一个子节点的值。
2. 每个节点的左子树和右子树都是一个堆。

堆分为最大堆和最小堆，根据它们的性质可以快速找到最大或最小值。以下是用 C 语言实现最大堆的代码：

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100

int heap[MAX_SIZE];
int size = 0;

// 交换两个元素的位置
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 向上调整堆
void sift_up(int i) {
    while (i > 0 && heap[i] > heap[(i - 1) / 2]) {
        swap(&heap[i], &heap[(i - 1) / 2]);
        i = (i - 1) / 2;
    }
}

// 向下调整堆
void sift_down(int i) {
    int max_index = i;
    int left = i * 2 + 1;
    int right = i * 2 + 2;

    if (left < size && heap[left] > heap[max_index]) {
        max_index = left;
    }

    if (right < size && heap[right] > heap[max_index]) {
        max_index = right;
    }

    if (i != max_index) {
        swap(&heap[i], &heap[max_index]);
        sift_down(max_index);
    }
}

// 插入元素
void insert(int x) {
    if (size == MAX_SIZE) {
        printf("Heap is full.\n");
        return;
    }

    heap[size] = x;
    size++;
    sift_up(size - 1);
}

// 删除堆顶元素
int pop() {
    if (size == 0) {
        printf("Heap is empty.\n");
        return -1;
    }

    int root = heap[0];
    heap[0] = heap[size - 1];
    size--;
    sift_down(0);
    return root;
}

int main() {
    insert(3);
    insert(2);
    insert(1);
    printf("%d\n", pop()); // 输出 3
    printf("%d\n", pop()); // 输出 2
    printf("%d\n", pop()); // 输出 1
    printf("%d\n", pop()); // 输出 Heap is empty.
    return 0;
}

这个实现中，我们使用了一个数组来存储堆的元素，使用一个变量 `size` 来表示堆的大小，插入元素时先将元素放到数组最后，然后向上调整堆，删除堆顶元素时将最后一个元素放到堆顶，然后向下调整堆。这个实现中，我们使用了递归来向下调整堆，也可以使用循环来实现。

建立二叉排序树以及进行查找、插入、删除等操作的算法的代码

以下是基于C++语言的二叉排序树的实现：

#include<iostream>
using namespace std;

//定义二叉树结点结构
struct TreeNode {
    int data;
    TreeNode* left;
    TreeNode* right;
};

//初始化根节点为空
TreeNode* root = nullptr;

//插入节点
void insertNode(int value) {
    //如果根节点为空，则创建一个新节点作为根节点
    if (root == nullptr) {
        root = new TreeNode;
        root->data = value;
        root->left = nullptr;
        root->right = nullptr;
        return;
    }
    //否则遍历树，找到合适的位置插入新节点
    TreeNode* node = root;
    while (node != nullptr) {
        if (value < node->data) {
            if (node->left == nullptr) {
                node->left = new TreeNode;
                node->left->data = value;
                node->left->left = nullptr;
                node->left->right = nullptr;
                return;
            }
            else {
                node = node->left;
            }
        }
        else {
            if (node->right == nullptr) {
                node->right = new TreeNode;
                node->right->data = value;
                node->right->left = nullptr;
                node->right->right = nullptr;
                return;
            }
            else {
                node = node->right;
            }
        }
    }
}

//查找节点
TreeNode* searchNode(int value) {
    TreeNode* node = root;
    while (node != nullptr) {
        if (node->data == value) {
            return node;
        }
        else if (value < node->data) {
            node = node->left;
        }
        else {
            node = node->right;
        }
    }
    return nullptr;
}

//删除节点
void deleteNode(int value) {
    //查找要删除的节点
    TreeNode* node = root;
    TreeNode* parentNode = nullptr;
    while (node != nullptr) {
        if (node->data == value) {
            break;
        }
        else if (value < node->data) {
            parentNode = node;
            node = node->left;
        }
        else {
            parentNode = node;
            node = node->right;
        }
    }
    //如果未找到要删除的节点，则直接返回
    if (node == nullptr) {
        return;
    }
    //如果要删除的节点有两个子节点
    if (node->left != nullptr && node->right != nullptr) {
        //查找右子树中最小的节点
        TreeNode* minNode = node->right;
        TreeNode* minParentNode = node;
        while (minNode->left != nullptr) {
            minParentNode = minNode;
            minNode = minNode->left;
        }
        //将右子树中最小的节点的值赋给要删除的节点
        node->data = minNode->data;
        //将要删除的节点变为右子树中最小的节点
        node = minNode;
        parentNode = minParentNode;
    }
    //如果要删除的节点只有一个子节点或者没有子节点
    TreeNode* childNode = nullptr;
    if (node->left != nullptr) {
        childNode = node->left;
    }
    else if (node->right != nullptr) {
        childNode = node->right;
    }
    //如果要删除的节点没有子节点，则将其父节点的对应子节点指针设为nullptr
    if (childNode == nullptr) {
        if (parentNode == nullptr) {
            root = nullptr;
        }
        else if (node == parentNode->left) {
            parentNode->left = nullptr;
        }
        else {
            parentNode->right = nullptr;
        }
        delete node;
    }
    //如果要删除的节点只有一个子节点，则将其父节点的对应子节点指针设为其子节点
    else {
        if (parentNode == nullptr) {
            root = childNode;
        }
        else if (node == parentNode->left) {
            parentNode->left = childNode;
        }
        else {
            parentNode->right = childNode;
        }
        delete node;
    }
}

//中序遍历
void inorderTraversal(TreeNode* node) {
    if (node == nullptr) {
        return;
    }
    inorderTraversal(node->left);
    cout << node->data << " ";
    inorderTraversal(node->right);
}

int main() {
    insertNode(5);
    insertNode(3);
    insertNode(7);
    insertNode(1);
    insertNode(9);
    insertNode(4);
    insertNode(2);
    
    cout << "中序遍历结果为：";
    inorderTraversal(root);
    cout << endl;
    
    TreeNode* node = searchNode(7);
    if (node != nullptr) {
        cout << "查找结果：" << node->data << endl;
    }
    else {
        cout << "未找到该节点" << endl;
    }
    
    deleteNode(5);
    cout << "删除节点后中序遍历结果为：";
    inorderTraversal(root);
    cout << endl;
    
    return 0;
}

以上代码实现了二叉排序树的插入节点、查找节点、删除节点和中序遍历等操作。其中，插入节点和删除节点的实现都需要遍历整棵树，时间复杂度为O(log n)。而查找节点的时间复杂度也为O(log n)。