algorithm - 如何使用存储在叶子中的给定元素构建堆？

Question

我有 n 个数字，我需要构建一个堆数据结构，以便所有 n 个数字将存储在堆的叶节点中，并且所有内部节点将存储存储在以该内部节点为根的左子树或右子树中的最小数字。

请建议我一个有效的算法。

Answer 1

这是你在找的吗？这里节点 i 的子节点是 2*i 和 2*i+1。还假设 n 是 2 的幂，但可以推广。

int* create_heap(int* input , int n ){

    int * heap = (int*) malloc(sizeof(int)*2*n);

    for(int i = n ; i<2*n ; i++){
       heap[i] = a[i-n];
    }

    for(int i=n-1 ; i>0 ; i--){
        heap[i] = heap[2*i] < heap[2*i+1] ? heap[2*i] : heap[2*i+1];
    }
    return heap;

}

Answer 2

您可以将数据结构建立在获胜者树的概念上。看看链接，看看它是如何运作的。

http://www.geeksforgeeks.org/tournament-tree-and-binary-heap/