堆排序手写堆

xiaoxiao2021-02-28  151

堆排序: 1,开始建堆,已一个小根堆为例:(图片摘自别人,与下面的排序代码无关)


构造好了堆之后,下面就是排序的过程:



直接上代码了:

public class HeapSort { public void sift(int[] arr, int index, int length){ int temp = arr[index];//先取出当前元素i for(int k=index*2+1; k<length; k=k*2+1){//从i结点的左子结点开始,也就是2i+1处开始 if(k+1<length && arr[k]<arr[k+1]){//如果左子结点小于右子结点,k指向右子结点 k++; } if(arr[k] >temp){//如果子节点大于父节点,将子节点值赋给父节点(不用进行交换) arr[index] = arr[k]; index = k; }else{ break; } } arr[index] = temp;//将temp值放到最终的位置 } public void sort(int[] arr){ for(int i=arr.length/2-1;i>=0;i--){ //从第一个非叶子结点从下至上,从右至左调整结构 sift(arr,i,arr.length); } //2.调整堆结构+交换堆顶元素与末尾元素 for(int j=arr.length-1;j>0;j--){ swap(arr,0,j);//将堆顶元素与末尾元素进行交换 sift(arr,0,j);//重新对堆进行调整 } } public void swap(int[] arr, int i, int j){ int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } public static void main(String[] args) { int[] arr = {1,43,6,4,3,2,5}; new HeapSort().sort(arr); System.out.println(Arrays.toString(arr)); } }

由于是从第二个元素开始排序的也就是a[1],所以第一个元素没有排序,可以在初始化的时候声明为0。


2017/8/7/13:32

今天在算法导论上看到一种用递归实现的方法,只需要把上面的sift方法换一下即可:

void sift2(int a[],int m,int n) { int i = m,j = 2*m,k=2*m+1; int largest; if(largest > n)return; if(a[i]>a[j])largest = i; else j = largest; if(a[k]>a[largest]) largest = k; if(i!= largest) { swaps(&a[i],&a[largest]); sift2(a,largest,n); } }

2020.12.2,时隔三年,再对堆进行一遍温习,以大根堆为例:

初始化一个堆:

private int capacity; private int size; private int[] data; private int swapindex; // 待交换的元素索引 public Heap(int capacity){ this.capacity = capacity; this.size = 0; this.data = new int[capacity+1]; this.swapindex = capacity; } }

向堆中插入一个元素

public void insert(int val){ if(size == capacity) { System.out.println("heap is full"); return; } data[++size] = val; siftUp(size); }

移除堆顶元素并返回:

public int removeTop(){ if(size == 0) { System.out.println("heap is empty"); return -1; } int res = data[1]; size--; data[1] = data[swapindex]; data[swapindex] = res; siftdown(1); swapindex--; return res; }

插入的话,向上筛选,移除的话,交换顶端元素后向下筛选

private void siftUp(int i) { while(i > 1 && data[i] > data[i/2]){ int temp = data[i]; data[i] = data[i/2]; data[i/2] = temp; i >>= 1; } } private void siftdown(int i) { while(2*i <= size){ int j = 2 * i; if(j+1 <= size && data[j] < data[j+1]) j++; if(data[i] > data[j]) break; int t = data[i]; data[i] = data[j]; data[j] = t; i = j; } }

总体代码如下:

import java.util.Arrays; public class Heap { private int capacity; private int size; private int[] data; private int swapindex; public Heap(int capacity){ this.capacity = capacity; this.size = 0; this.data = new int[capacity+1]; this.swapindex = capacity; } public void insert(int val){ if(size == capacity) { System.out.println("heap is full"); return; } data[++size] = val; siftUp(size); } private void siftUp(int i) { while(i > 1 && data[i] > data[i/2]){ int temp = data[i]; data[i] = data[i/2]; data[i/2] = temp; i >>= 1; } } public int removeTop(){ if(size == 0) { System.out.println("heap is empty"); return -1; } int res = data[1]; size--; data[1] = data[swapindex]; data[swapindex] = res; siftdown(1); swapindex--; return res; } private void siftdown(int i) { while(2*i <= size){ int j = 2 * i; if(j+1 <= size && data[j] < data[j+1]) j++; if(data[i] > data[j]) break; int t = data[i]; data[i] = data[j]; data[j] = t; i = j; } } public static void main(String[] args) { int[] a = {100,6,3,1,7,5,6,8}; Heap hp = new Heap(a.length); for(int v: a){ hp.insert(v); } System.out.println(Arrays.toString(hp.data)); for(int i = 0; i<a.length; i++) System.out.print(hp.removeTop()+" "); } }
转载请注明原文地址: https://www.6miu.com/read-50935.html

最新回复(0)