堆的认识

堆的认识

• 首先需要说明一点的问题是，这里我们所说的堆和使用malloc开辟的内存空间的那个堆，是完全不一样的，使用malloc的哪个堆，相当于是一块内存空间，而我们这里所说的堆，其实是一种数据结构，也是二叉树顺序存储最明显的一个例子

堆的概念及结构

• 如果有一个关键码的集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且 Ki >= K2i+2) i = 0，1，2…，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
  

堆的性质

• 堆中某个节点的值总是不大于或不小于其父节点的值；
• 堆总是一棵完全二叉树
• 堆顶元素一定是最大的或者最小的

举例

• 上面的结构，已经是一个小堆的结构了，但是，我们现在修改一下堆顶的元素，把堆顶的元素修改成100(如下所示)，然后现在看的话，这个树型的结构就既不是大堆也不是小堆了，因为堆顶的结点不满足小堆的性质
  
• 如果我们还希望把其当作堆来处理的话，那么我们就需要对上面的树型结构进行调整。我们需要将100进行向下调整，调整到一个什么情况呢，我们需要将100调整到属于他的位置，从而上面树型结构可以看成是一个堆的结构
• 那么就需要将100进行向下调整，那么理所当然的，100的孩子就需要向上进行调整，在100的孩子里面选择一个较小的孩子，进行向上调整
  
• 上面的只是一个大致的调整过程，里面其实还是存在有一些问题的，我们会继续向下探究
  

堆向下调整的时间复杂度是多少？-

• 堆向下调整的时间复杂度是O(logn),因为从上到下移动的其实就是一棵树的高度(最差的情况下)，所以，其实就相当于是在求树的高度

再举一个例子

• 上面的哪个例子，之所以可以非常顺利的完成交换从而成为堆结构，是因为他的左子树和右子树，其实都已经是小堆的结构了，而上面这个例子的这棵树，他其实不能像上面的那个例子经过简单的交换就成为堆结构的，因为他的左右子树都不满足成为堆的结构，即使交换使得一边成为真正的堆结构，但是另一边，仍然不是堆的结构，向下调整parent的时候，必须保证parent的左右孩子是堆的结构，比如说，如果想要动8的话，那么需要先对他的子树进行调整。
• 那么，现在来看一下，真正的建堆过程到底是什么样子的。
• 得出的结论就是，如果你在调整一个树型结构的东西的话，其实是不能从堆顶元素开始调整的，应该从最后一个双亲结点开始调整，这样子的话，就可以确保每一个结点都被访问到，都被调整的，这样子的话，最终才会形成一个大堆或者说是一个小堆。
• 所以说，上面的那一棵树，其实应该是需要从5那个结点开始进行调整的(从倒数第一个非叶子节点开始调整)