?? heapalgorithm.java
字號:
/**
* A Heapsort demonstration algorithm
* HeapAlgorithm.java, 19.04.97
*
* @author Lars Marius Garshol
* @version 1.00 - 19.04.97
*/
class HeapAlgorithm extends SortAlgorithm {
void sort(int a[]) throws Exception {
int i,tmp;
//----Step 1: Make a heap in linear time. Top of heap at top of array.
// Largest numbers at the top
for (i=a.length/2; i>=0; i--) {
perc_down(i,a,a.length-1);
}
//----Step 2: Take out elements one by one, largest first, and put them at the bottom
for (i=a.length-1; i>=0; i--) {
delete_max(i,a); //Places max element at a[i]
}
}
void delete_max(int ix, int a[]) throws Exception {
int ret;
ret=a[0]; //Return value
a[0]=a[ix];
perc_down(0,a,ix-1); //Percolate last value down
a[ix]=ret;
}
//Have to go to i*2+1 and i*2+2 because we start at 0
//lng is the last index we can touch, the end of the heap
void perc_down(int ix, int a[], int lng) throws Exception {
int i,tmp;
tmp=a[ix];
i=ix;
while (i*2+1<=lng) {
if (i*2+1==lng || a[i*2+1]>a[i*2+2]) {
if (a[i*2+1]<tmp) break; //Position found
a[i]=a[i*2+1];
i=i*2+1;
} else {
if (a[i*2+2]<tmp) break; //Position found
a[i]=a[i*2+2];
i=i*2+2;
}
pause(i,ix);
}
a[i]=tmp;
}
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -