資訊專欄INFORMATION COLUMN
摘要：如果有一個(gè)關(guān)鍵字的集合把所有元素按完全二叉樹的順序存儲(chǔ)方式存放在一個(gè)一維數(shù)組中，并且滿足且向上取整則稱這個(gè)集合為小根堆。
如果有一個(gè)關(guān)鍵字的集合K={k0,k1,k2, ..., kn-1}, 把所有元素按完全二叉樹的順序存儲(chǔ)
方式存放在一個(gè)一維數(shù)組中，并且滿足
ki <= k2i+1 且 ki <= k2i+2 (i = 0, 1, ..., (n-2)/2 向上取整)
則稱這個(gè)集合為小根堆。
創(chuàng)建
復(fù)制堆數(shù)組
找到最初的調(diào)整位置，即最后一個(gè)分支結(jié)點(diǎn)
自底向上逐步擴(kuò)大形成堆
向前換一個(gè)分支結(jié)點(diǎn)
插入
將待插入元素插入已建成堆的最后面
沿著出入位置所在的分支逐步向上調(diào)整
刪除
將頂元素刪除
將數(shù)組中最后一個(gè)元素放到堆頂
自頂向下調(diào)整
代碼實(shí)現(xiàn)
import java.util.Arrays;
/**
* Created by mico on 2017/2/5.
*/
public class HeapExam {
/**
* 小根堆初始化
*
* @param a
* @param length
*/
public void minHeap(int a[], int length) {
for (int i = length >> 1; i >= 0; i--) {
adjustMinHeap(a, length, i);
}
}
/**
* 排序 topn
*
* @param a
* @param length
*/
public void sort(int a[], int length) {
for (int i = 0, last = length; i < length - 1; i++) {
swap(a, 0, --last);
minHeap(a, last);
}
}
/**
* 小根堆調(diào)整
*
* @param a
* @param length
* @param i
*/
private void adjustMinHeap(int[] a, int length, int i) {
int left = 2 * i + 1;
int right = 2 * i + 2;
int minIndex = i;
if (left < length && a[left] < a[i]) {
minIndex = left;
}
if (right < length && a[right] < a[minIndex]) {
minIndex = right;
}
if (minIndex != i) {
swap(a, i, minIndex);
adjustMinHeap(a, length, minIndex);
}
}
/**
* 交換 數(shù)組值
*
* @param a
* @param i
* @param j
*/
private void swap(int[] a, int i, int j) {
a[i] = a[i] + a[j];
a[j] = a[i] - a[j];
a[i] = a[i] - a[j];
}
}
測(cè)試
public static void main(String[] args) {
int[] a = {153, 173, 728, 9, 425, 165, 7, 233};
//int[] arry_int={13, 38, 27, 55, 76, 65, 49, 97};
HeapExam exam = new HeapExam();
exam.minHeap(a, a.length);
System.out.println("小根堆：" + Arrays.toString(a));
exam.sort(a, a.length);
System.out.println("排序結(jié)果：" + Arrays.toString(a));
}
輸出
小根堆：[7, 9, 153, 173, 425, 165, 728, 233] 排序結(jié)果：[728, 425, 233, 173, 165, 153, 9, 7]
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://m.specialneedsforspecialkids.com/yun/66578.html
摘要：前面介紹了七大算法的思想與實(shí)現(xiàn)步驟，下面來做一個(gè)歸總。直到無序區(qū)中的數(shù)為零，結(jié)束排序。步驟以從小到大為例，排序數(shù)組大小為。比較完以后則排序結(jié)束。堆排序思想堆排序是采用樹的形式的數(shù)據(jù)結(jié)構(gòu)來進(jìn)行排序的，其中每一個(gè)堆都是完全二叉樹。 前面介紹了七大算法的思想與實(shí)現(xiàn)步驟，下面來做一個(gè)歸總。 排序方法 平均復(fù)雜度 最壞復(fù)雜度 最好復(fù)雜度 輔助空間 穩(wěn)定性 直接選擇排序 O(n^2...
摘要：排序代碼實(shí)現(xiàn)和一概念排序算法的穩(wěn)定性穩(wěn)定性穩(wěn)定排序算法會(huì)讓原本有相等鍵值的紀(jì)錄維持相對(duì)次序。交換的結(jié)果導(dǎo)致結(jié)點(diǎn)的值變化了，重復(fù)，，的操作，直到?jīng)]有孩子時(shí)跳出代碼實(shí)現(xiàn)構(gòu)建初始堆堆排序算法思想大頂堆舉例將待排序的序列構(gòu)造成一個(gè)大頂堆。 排序 代碼實(shí)現(xiàn)：Java 和 Python 一、概念 1.1 排序算法的穩(wěn)定性 穩(wěn)定性：穩(wěn)定排序算法會(huì)讓原本有相等鍵值的紀(jì)錄維持相對(duì)次序。也就是如果一個(gè)排序...
摘要：排序代碼實(shí)現(xiàn)和一概念排序算法的穩(wěn)定性穩(wěn)定性穩(wěn)定排序算法會(huì)讓原本有相等鍵值的紀(jì)錄維持相對(duì)次序。交換的結(jié)果導(dǎo)致結(jié)點(diǎn)的值變化了，重復(fù)，，的操作，直到?jīng)]有孩子時(shí)跳出代碼實(shí)現(xiàn)構(gòu)建初始堆堆排序算法思想大頂堆舉例將待排序的序列構(gòu)造成一個(gè)大頂堆。 排序 代碼實(shí)現(xiàn)：Java 和 Python 一、概念 1.1 排序算法的穩(wěn)定性 穩(wěn)定性：穩(wěn)定排序算法會(huì)讓原本有相等鍵值的紀(jì)錄維持相對(duì)次序。也就是如果一個(gè)排序...
閱讀 1125·2021-11-25 09:43
閱讀 1647·2021-09-13 10:25
閱讀 2610·2021-09-09 11:38
閱讀 3414·2021-09-07 10:14
閱讀 1725·2019-08-30 15:52
閱讀 647·2019-08-30 15:44
閱讀 3584·2019-08-29 13:23
閱讀 1980·2019-08-26 13:33
