1 堆
堆是一种特殊的二叉树数据结构，它是一颗完全二叉树，即直到最后一个叶子节点，中间没有空缺节点。 由于堆是完全二叉树，那么就可以使用线性数据结构数组来进行表示： 当直到根节点的索引时，可以计算出左右子树的节点索引：
parentIndex
= i
;
leftChildIndex
= 2 * i
+1;
rightChildIndex
= 2 *i
+2;
当直到子节点的索引时，可以直到父节点的索引：
if leftChildIndex
= i
parentIndex
= (leftChildIndex
- 1) / 2;
if rightChildIndex
= i
parentIndex
= (rightChildIndex
- 2) / 2;
2 最大堆和最小堆
最大堆就是当前根节点的值总是最大值，最小堆就是当前根节点的值总是最小值。
2.1 最大堆Java实现
public class MaxHeap {
private int[] a
;
public MaxHeap(int[] a
) {
this.a
= a
;
}
public void buildMaxHeap(){
int n
= this.a
.length
;
for (int i
= (int)(n
-2)/2; i
>=0 ; i
--) {
downAdjust(i
,n
);
}
}
public int[] getHeap(){
return this.a();
}
private void downAdjust(int pIndex
,int n
){
int childIndex
= 2*pIndex
+1;
int tem
= this.a
[pIndex
];
while (childIndex
< n
){
if (childIndex
+ 1 < n
&& this.a
[childIndex
+1] > this.a
[childIndex
])
childIndex
++;
if (tem
> this.a
[childIndex
])
break;
this.a
[pIndex
] = this.a
[childIndex
];
pIndex
= childIndex
;
childIndex
= 2 * childIndex
+ 1;
}
this.a
[pIndex
] = tem
;
}
}
2.2 最小堆Java实现
public class MinHeap{
private int[] a
;
public MinHeap(int[] a
) {
this.a
= a
;
}
public void buildMinHeap(){
int n
= this.a
.length
;
for (int i
= (int)(n
-2)/2; i
>-1 ; i
--) {
downAdjust(i
,n
);
}
}
public int[] getHeap(){
return this.a();
}
private void downAdjust(int pIndex
,int n
){
int childIndex
= 2*pIndex
+1;
int tem
= this.a
[pIndex
];
while (childIndex
< n
){
if (childIndex
+ 1 < n
&& this.a
[childIndex
+1] < this.a
[childIndex
])
childIndex
++;
if (tem
< this.a
[childIndex
])
break;
this.a
[pIndex
] = this.a
[childIndex
];
pIndex
= childIndex
;
childIndex
= 2 * childIndex
+ 1;
}
this.a
[pIndex
] = tem
;
}
}
