标签: max-heap

传统的Heapsort算法在每次之后将堆的最后一个元素与当前堆的根交换heapification,然后再次继续该过程.但是,我注意到它有点不必要.

在一个heapification子数组之后,当节点包含最高值(如果它是a max-heap)时,数组中接下来的2个元素必须跟随排序数组中的根,或者按照与现在相同的顺序,或者交换它们如果它们是反向排序的.因此,不是仅仅使用最后一个元素交换根,最好将前3个元素(包括节点和必要的第2和第3个元素的交换之后)与最后3个元素交换,以便2后续heapifications(第2和第3个元素)免除？

这个方法有什么不利之处(除了第二和第三个元素的if-need交换,这应该是微不足道的)？如果没有,如果它确实更好,它将带来多少性能提升？这是伪代码:

function heapify(a,i) {
  #assumes node i has two nodes, both heaps. However node i itself might not be a heap, i.e one of its children may be greater than its value.
  #if so, find the greater of its two children, then swp the parent with that value.
  #this might render that child as no longer a heap, so recurse
 }

function create_heap(a) {
   #all elements …

我有一个MaxPQ堆使用数组来存储元素.我可以使用什么算法来查找堆中的给定元素？我当前使用的算法迭代遍历索引1的数组,直到添加到堆中的元素数.该算法具有O(N)的复杂度,是否存在复杂度为O(logN)的算法？

我需要实现一个函数HEAP-DELETE-MIN(Array)来删除最大堆中的最小整数.我不是要求功能本身,但有人可以为我提供一些 伪代码来帮助我开始吗？这将是一个很大的帮助.该数组应该在函数末尾保持最大堆.

所以我正在尝试为练习实现最大堆,这样我就可以熟悉Go了.

type MaxHeap struct {
    slice []int
    heapSize int
}
func BuildMaxHeap(slice []int) MaxHeap{
    h := MaxHeap{slice: slice, heapSize: len(slice)}
    for i := len(slice)/2; i >= 0; i-- {
        h.MaxHeapify(i)
    }
    return h
}

func (h MaxHeap) MaxHeapify(i int) {
    left := 2*i
    right := 2*i + 1
    largest := i
    slice := h.slice

    if left < h.size() {
        if slice[left] > slice[i] {
            largest = left
        } else {
            largest = i
        }
    }
    if right < h.size() { …

CLRS 练习：6.5-8

该操作从堆中HEAP-DELETE(A,i)删除节点中的项目。给出一个针对 n 元素最大堆及时运行的实现。iAHEAP-DELETEO(lg n)

我想知道算法对于输入A[10]={84,22,19,21,3,10,6,5,20}（索引从1开始）和A[6]=10被删除是否错误。用替换最后一个节点A[6]将导致违反堆属性，忽略父值。

我为此编写了一个算法，想知道它是否正确或者我哪里出错了？

HEAP-DELETE(A,i)
  A[i]=A[A.heapsize]
  A.heapsize-=1
  while i>1 and A[parent(i)]<A[i]
    swap A[i] with A[parent(i)]
    i=parent(i);

我正在使用算法,特别是heapsort.根据我的理解,heapsort算法涉及通过首先将其转换为最大堆来准备列表.

转过身来

[2,8,5,3,9,1]

进入
[9,8,5,3,2,1]

使用heapsort我应该用1交换9.但是通过在最大堆积之后直接查看数组,我看到按降序排列的排序列表.当列表已按递减顺序排序时,为什么需要交换？

这只是我观看后的想法:https: //www.youtube.com/watch？v = 2DmK_H7IdTo

该代码在"算法简介"一书中给出.为此,我使用了1个索引数组

#include <cstdlib>
#include <iostream>

using namespace std;
int n=6;
int x[1000];

void max_heapify(int a[],int i)
{
    int left=2*i;
    int right=2*i+1;
    int largest=i;
    if( left<=n && a[left]>a[largest]){
        largest=left;

    }
    if(right<=n &&  a[right]>a[largest])
    {
        largest=right;

    }
    if(largest!=i)
    {
        int t=a[i];
        a[i]=a[largest];
        a[largest]=t;

    }
    max_heapify(a,largest);
}
void max_heap(int a[])
{
    int heap_length=n;
    for(int i=n/2;i>=1;i--)
        max_heapify(a,i);

}
int main(int argc, char *argv[])
{
    for(int i=1;i<=n;i++)
        cin>>x[i];
    max_heap(x);
    cout<<endl;

    for(int i=1;i<=n;i++)
        cout<<x[i]<<"  ";
    // system("PAUSE");
    //return EXIT_SUCCESS;
    return 0;
}

对于这个输入

1 5 7 …