二进制堆 - 如何以及何时使用 max-heapify

Question

我正在阅读有关堆数据结构的内容，但我不知道何时使用 max heapify 函数以及原因。

我编写了一个插入函数，该函数始终将堆保持为最大堆，但我看不到何时会使用最大堆。

你能解释一下吗？ 谢谢

这是我的代码：

  int  PARENT(int i) {
    return i/2;
  }

  int LEFT(int i) {
    return 2*i;
  }
  
  int RIGHT(int i ) {
    return 2*i +1;
  }

  void max_heapify(int *v, int index, int heapsize) {
    int largest;
    int left = LEFT(index);
    int right = RIGHT(index);
  
    if (left<heapsize && v[left] > v[index])
      largest = left;
    else 
      largest = index;
  
    if (right < heapsize && v[right] > v[largest])
      largest = right;
  
    if (largest !=index) {
      v[index]  = v[index] ^v[largest];
      v[largest] = v[index] ^v[largest];
      v[index] = v[index] ^v[largest];
      max_heapify(v,largest,heapsize);
    }
  }

  void insert(int *v, int * length, int value) {
    v[++*length] = value;
    int valuePos = *length;
    int parent = PARENT(valuePos);

    if (parent!=valuePos) {
      while (v[parent] < v[valuePos]) {
        v[parent] = v[parent] ^ v[valuePos];
        v[valuePos] = v[parent] ^v[valuePos];
        v[parent] = v[parent] ^ v[valuePos];
        valuePos = parent;
        parent = PARENT(valuePos);
      }
    }
  }

Answer 1

将数组转为堆时应使用 heapify 算法。您可以通过将每个数组元素依次插入到一个新堆中来实现这一点，但这需要 O(n lg n) 时间，而 heapify 则需要 O(< em>n) 时间。

Answer 2

max_heapify 预计会在常规数组上调用，以使其成为堆。 insert 负责维护工作，这需要数组（函数中的v）已经是一个堆。

Answer 3

正如您所说，max-heapify 函数是一个通用的heapify 函数（堆可以使用任何有效的比较函数来对其元素进行排序）。它旨在用作从数组构造堆的 init 函数。

处理堆的函数的复杂性（及其预期用途）：

• init (max-heapify)：O(n) ，使用从排序序列（数组）（最大排序，在您的情况下）初始化堆
• insert ： O(lg n) ，使用在堆中插入单个元素（维护堆树“排序”）
• delete ： O(lg n) ，用于从堆中删除“最佳”（在您的情况下是最大）元素（维护堆树“排序”）

但是，由于这个问题被标记为C++，您还应该考虑使用std::set 来自 STL，而不是实现您自己的堆。所考虑的操作的复杂性与任何堆实现相同，并且它可以轻松地使用任何比较函数（预先编写的或用户编写的）进行操作。堆实现的另一个优点是它是一个排序容器，您可以轻松地迭代排序顺序中的所有元素（而不仅仅是第一个元素），而不会破坏结构。

std::set 的唯一问题是它是一个唯一的容器 - 这意味着其中只能存在具有相同键的元素的 1 个副本。但也有一个解决方案 - std::multiset 使用相同的键保留多个对象的排序实例。

另外，根据您所需的使用情况（如果有大量与搜索键关联的数据），您可能还想尝试 std::map 或 std::multimap。

如果您想实现自己的堆实现，并且您的目的是充分使用 C++，我强烈建议您将其放入单独的类（甚至命名空间）中。如果您只想保持实现的原样，您应该考虑将问题重新标记为 C

Answer 4

您需要像数组一样将数据随机插入堆中。之后你可以调用 max heapify 函数来保留 Max Heap 的属性。这是我的代码

class max_heap{  
 private:               // are the private members of class
      int *arr;
      int size;
      int ind;
};

        void max_heap::bubbledown(int *ar, int i)
        {
         int len = ind - 1;
         int lt = 2 * i;
         int rt = lt + 1;
         while (lt <= len && rt <= len)                                         
         {
            if (arr[i] > arr[lt] && arr[i] > arr[rt])
                break;

            else if (ar[lt] > ar[rt])
            {
                if (ar[i] < ar[lt]){
                    swap(ar[i], ar[lt]);
                    i = lt;
                    lt = 2 * i;
                }
            }
            else if (ar[lt] < ar[rt])
            {
                if (ar[i] < ar[rt]){
                    swap(ar[i], ar[rt]);
                    i = rt;
                    rt = (2 * i)+1;
                }
            }
        }
    }

    void max_heap::heapify()
    {
        int len = ind - 1;
        for (int i = len; i >= 1 && (i/2) >= 1; i--)
        {
            if (arr[i] > arr[i/2])
            {
                swap(arr[i], arr[i/2]);
                bubbledown(arr, i);
            }
        }
    }