时间戳

首页 > 解决方案 > 如何使用 buildHeap 方法和 insert 方法构建最小堆？

c++ - 如何使用 buildHeap 方法和 insert 方法构建最小堆？

问题描述

我是编程新手 我想了解什么是最小堆以及如何使用buildHeap方法和insert方法找到给定数组的最小堆

标签： c++arraysheap

解决方案

要学习最小堆，您必须首先了解二进制堆是什么。
二叉堆是具有以下属性的二叉树。
1）它是一棵完整的树（除了可能的最后一层，所有层都被完全填满，最后一层的所有键都尽可能左）。二叉堆的这一特性使它们适合存储在数组中。

2) 二叉堆是最小堆或最大堆。在最小二叉堆中，根处的键必须是二叉堆中所有键中的最小值。对于二叉树中的所有节点，相同的属性必须递归地为真。
要将元素“K”插入最小堆：

void MinHeap::insertKey(int k)
{
    if (heap_size == capacity)
    {
        cout << "\nOverflow\n";
        return;
    }
    heap_size++;
    int i = heap_size - 1;
    harr[i] = k;
    while (i != 0 && harr[parent(i)] > harr[i])
    {
       swap(&harr[i], &harr[parent(i)]);
       i = parent(i);
    }
}

我不知道任何buildheap或insert功能，但 c++ stl 具有make_heap()和push_heap()功能相同的目的。 堆 c++ 实现

推荐阅读