不同的堆操作实际上意味着什么？

Question

有许多堆操作，并给出了一些相同操作的各种名称。

我被名字和别名压倒了。

所以，请澄清一下，什么是下面堆的操作之间的差异/相似之处/关系：

(1) Heapify 
(2) Insert 
(3) Delete 
(4) Shift-up 
(5) Shift-down 

例如，一些资源谈论使用减档执行堆排序;而有些则使用Heapify实现相同的算法。有些甚至使用Delete实现它。

Answer 1

1）Heapify恢复堆条件。例如，如果您更改了树中的节点，则条件无效。如果您在树上向上或向下移动节点，则可以恢复该条件。

2）将在树

3的节点）删除节点在树中

4）移动的节点向上的树中，只要需要（取决于堆条件：分钟-heap或最大堆）

5）移动节点倒在树中，类似4）

这也可能是最好的，如果你尝试实施或了解真正的代码，并且不用担心的命名。 。

Answer 2

偷看过维基百科，你可以得到堆各种各样的信息：

http://en.wikipedia.org/wiki/Heap_%28data_structure%29

Answer 3

要添加注释以由@ duedl0r回答，使用什么向上移位和向下移位来堆叠当前结构。因此，例如。在最小堆的情况下，当插入树中小于某些节点的元素时，数据结构现在不会遵循堆条件（在最小堆的情况下，父元素的值应小于其子元素），所以你必须升高。

所以在代码方面：

public void insert(int value) { 
    if (heapSize == data.length) 
     throw new HeapException("Heap's underlying storage is overflow"); 

    else { 
     heapSize++; 
     data[heapSize - 1] = value; 
     siftUp(heapSize - 1); 
    } 

}  

private void siftUp(int nodeIndex) { 
    int parentIndex, tmp; 
    if (nodeIndex != 0) { 
     parentIndex = getParentIndex(nodeIndex); 
     /*if parent index data is more than child data, swap*/ 
     if (data[parentIndex] > data[nodeIndex]) { 
      tmp = data[parentIndex]; 
      data[parentIndex] = data[nodeIndex]; 
      data[nodeIndex] = tmp; 
      siftUp(parentIndex); 
     } 
    } 

} 

数据是resemple堆的阵列，并且堆大小是当前地方新元素将被存储，并告诉这么多堆已满。

同样在删除的情况下，你必须使用下移来重构你的堆。