请教关于build heap BIG-O的问题# JobHunting - 待字闺中
d*i
1 楼
小弟请大哥们指教，谢谢。
以下两种build heap的方法。
第一种用PriorityQueue建的heap,请问是O(n)还是O(nlogn)?
第二种不用PriorityQueue,请问是是O(n)还是O(nlogn)。
第一种：
PriorityQueue minHeap = new PriorityQueue();
for (int i : a) {
minHeap.add(i);
}
第二种：
public static void buildMaxHeap(int[] a) {
int i = (a.length - 1) >> 1;
while (i >= 0) {
maintainMaxHeap(a, a.length, i);
i--;
}
}
public static void maintainMaxHeap(int[] a, int heapSize, int i) {
int l = (i << 1) + 1;
int r = (i << 1) + 2;
int parentMax = i;
if (l < heapSize && a[l] > a[parentMax]) {
parentMax = l;
}
if (r < heapSize && a[r] > a[parentMax]) {
parentMax = r;
}
if (parentMax != i) {
swap(a, parentMax, i);
maintainMaxHeap(a, heapSize, parentMax);
}
}
以下两种build heap的方法。
第一种用PriorityQueue建的heap,请问是O(n)还是O(nlogn)?
第二种不用PriorityQueue,请问是是O(n)还是O(nlogn)。
第一种：
PriorityQueue
for (int i : a) {
minHeap.add(i);
}
第二种：
public static void buildMaxHeap(int[] a) {
int i = (a.length - 1) >> 1;
while (i >= 0) {
maintainMaxHeap(a, a.length, i);
i--;
}
}
public static void maintainMaxHeap(int[] a, int heapSize, int i) {
int l = (i << 1) + 1;
int r = (i << 1) + 2;
int parentMax = i;
if (l < heapSize && a[l] > a[parentMax]) {
parentMax = l;
}
if (r < heapSize && a[r] > a[parentMax]) {
parentMax = r;
}
if (parentMax != i) {
swap(a, parentMax, i);
maintainMaxHeap(a, heapSize, parentMax);
}
}