找到無(wú)序數(shù)組的第K大的數(shù)匿级,實(shí)現(xiàn)思路有很多種融求,我們這次嘗試下使用堆來(lái)實(shí)現(xiàn)稠肘。
時(shí)間復(fù)雜度 O(nlogk)
public static void main(String[] args) {
int[] nums = { 1 ,3 ,4 ,8 ,9 ,7};
// 模擬新元素直接入堆頂猖毫,然后調(diào)整堆頂位置
nums[0] = 5;
adjustHeap(nums, 0, nums.length-1);
for (int num : nums) {
System.out.println(num);
}
}
/**
* @param nums
* @param adjustIndex 需要調(diào)整的位置
* @param maxIndex 堆最大的size
*/
public static void adjustHeap(int[] nums ,int adjustIndex ,int maxIndex) {
int index = adjustIndex * 2 + 1;
while (index <= maxIndex) {
if ((index + 1) < maxIndex && nums[index] > nums[index + 1]) {
index++;
}
if (nums[adjustIndex] > nums[index]) {
int temp = nums[index];
nums[index] = nums[adjustIndex];
nums[adjustIndex] = temp;
adjustIndex = index;
index = adjustIndex * 2 + 1;
} else {
break;
}
}
}
Heap的一般操作
package com.baidu.adu.common.benchmark;
import java.util.Arrays;
import java.util.List;
public class Heap {
private Node[] heapArray;
private int maxSize;
private int currentSize;
public int i1 = 0;
public int i2 = 0;
public Heap(int mx) {
maxSize = mx;
heapArray = new Node[maxSize];
currentSize = 0;
}
public boolean isEmpty() {
return currentSize == 0;
}
public boolean insert(int key) {
if (currentSize == maxSize)
return false;
Node thenode = new Node(key);
heapArray[currentSize] = thenode;
trickleUp(currentSize++);
return true;
}
public void trickleUp(int index) {
int parent = (index - 1) / 2;
Node bottom = heapArray[index];
while (index > 0 && heapArray[parent].getkey() < bottom.getkey()) {
i1++;
heapArray[index] = heapArray[parent];
index = parent;
parent = (parent - 1) / 2;
}
heapArray[index] = bottom;
}
public Node remove() {
Node root = heapArray[0];
heapArray[0] = heapArray[--currentSize];
trickleDown(0);
return root;
}
public void trickleDown(int index) {
int largeChild;
Node top = heapArray[index];
while (index < currentSize / 2) {
i2++;
int leftChild = 2 * index + 1;
int rightChild = 2 * index + 2;
if (rightChild < currentSize && heapArray[leftChild].getkey() < heapArray[rightChild].getkey())
largeChild = rightChild;
else
largeChild = leftChild;
if (top.getkey() >= heapArray[largeChild].getkey())
break;
heapArray[index] = heapArray[largeChild];
index = largeChild;
}
heapArray[index] = top;
}
public boolean change(int index, int newvalue) {
if (index < 0 || index >= currentSize)
return false;
int oldvalue = heapArray[index].getkey();
heapArray[index].setkey(newvalue);
if (oldvalue < newvalue)
trickleUp(index);
else
trickleDown(index);
return true;
}
public void displayHeap() {
System.out.print("heapArray:");
for (int i = 0; i < currentSize; i++) {
if (heapArray[i] != null)
System.out.print(heapArray[i].getkey() + " ");
else
System.out.print("--");
}
System.out.println("");
int nBlanks = 32;
int itemsPerrow = 1;
int column = 0;
int j = 0;
String dots = "........................";
System.out.println(dots + dots);
while (currentSize > 0) {
if (column == 0)
for (int i = 0; i < nBlanks; i++) {
System.out.print(" ");
}
System.out.print(heapArray[j].getkey());
if (++j == currentSize)
break;
if (++column == itemsPerrow) {
nBlanks /= 2;
itemsPerrow *= 2;
column = 0;
System.out.println();
} else
for (int i = 0; i < nBlanks * 2 - 2; i++)
System.out.print(' ');
}
System.out.println("\n" + dots + dots);
}
public int getRoot() {
return heapArray[0].getkey();
}
public static void main(String[] args) {
Heap h = new Heap(10);
List<Integer> list = Arrays.asList(44, 67, 33, 87, 15, 6, 24, 98, 65, 23, 45, 34, 4, 7, 9, 56, 35, 65, 12, 98);
h.insert(list.get(0));
h.insert(list.get(1));
h.insert(list.get(2));
h.insert(list.get(3));
h.insert(list.get(4));
h.insert(list.get(5));
h.insert(list.get(6));
h.insert(list.get(7));
h.displayHeap();
h.remove();
h.displayHeap();
}
}
package com.baidu.adu.common.benchmark;
public class Node {
private int iData;
public Node(int id) {
iData = id;
}
public int getkey() {
return iData;
}
public void setkey(int id) {
iData = id;
}
}