13：堆结构heap (priority queue)重要结构：上移过程heapInsert()

13：堆结构heap (priority queue)重要结构

　　　　　　　　　之

　　　　　　上移过程heapInsert()

1、堆结构就是用数组实现的完全二叉树结构；

2、完全二叉树中如果每棵树(包括子数) 的最大值都在顶部 是 大根堆；

3、完全二叉树中如果每棵树(包括子数) 的最小值都在顶部 是 小根堆；

4、堆结构的heapInsert  与 heapify操作；

5、堆结构的增大和减少；

6、优先级队列结构，就是堆结构；

完全二叉树的概念：

　　如果一棵树是满的，是完全二叉树；

　　如果一棵树不是满的，处在变慢的路上，从左往右依次变满的数；

       都是完全二叉树。

落地：使用连续数组来表示对应的完全二叉树，下标的表示。

                                           i的父节点(i-1)/2

                                               任何i位置

              左孩子的位置2*i+1                      右孩子的位置2*i+2     

 堆：1、是完全二叉树

　　2、是大根堆还是小根堆

 　　所以在数组中每次加入一个数，这个数会跟它的父进行比较，按照大小根堆的要求进行是否交换heapInsert（）。

 1 // 新加进来的数，现在停在了index位置，请依次往上移动，
 2         // 移动到0位置，或者干不掉自己的父亲了，停！
 3         private void heapInsert(int[] arr, int index) {
 4             // [index] [index-1]/2
 5             // index == 0
 6             while (arr[index] > arr[(index - 1) / 2]) {
 7                 swap(arr, index, (index - 1) / 2);
 8                 index = (index - 1) / 2;
 9             }
10         }