2

我正在阅读有关堆数据结构的信息，但我不知道何时使用 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);
      }
    }
  }
4

4 回答 4

1

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

于 2012-01-21T16:34:47.270 回答
0

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

于 2012-01-21T16:38:50.487 回答
0

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

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

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

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

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

此外，根据您所需的用途（与搜索键相关的数据很多），您可能还想尝试std::map或std::multimap.

如果您想制作自己的堆实现，我强烈建议您将它放在一个单独的类（甚至是命名空间）中，如果您打算C++充分利用它。如果您只是打算保持实现的形式，您应该考虑将问题重新标记为C

于 2012-01-21T17:02:32.167 回答
0

您需要像在数组中一样将数据随机插入堆中。之后你可以调用 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);
            }
        }
    }
于 2015-11-11T18:30:27.327 回答