频道栏目
首页 > 程序开发 > 软件开发 > Java > 正文
堆、堆排序及Java实现
2016-08-29 09:20:32         来源:fengrunche的博客  
收藏   我要投稿

一、堆

1、什么是堆?

堆是有如下特点的二叉树:

1)它是完全二叉树。即除了树的最后一层节点不需要是满的,其他的每层从左到右完全是满的。

2)它常常是数组实现的。

3)堆中的每个节点都必须满足堆的条件。

每个节点的关键字都不大于其子节点的关键字,这种堆称为小根堆。

每个节点的关键字都不小于其子节点的关键字,这种堆称为大堆根。本文采用此结构演示

综上所述,堆是一棵顺序存储的按照特定规则的完全二叉树。

\

数组的节点的索引为index,则:

1)它的父节点的下标为:(index-1)/2

2)它的左子节点的下表为:2*index + 1

3)它的左子节点的下表为:2*index + 2

2、堆与二叉搜索树的不同:

堆和二叉搜索树相比是弱序的。在二叉搜索树中,所有节点的关键字大于其左子树的关键字,小于其右子树的关键字。但是在堆中,每个节点都不小于其子节点,即从 根到叶子节点的每条路径都是降序排列的。

3、插入操作

1)将新增节点插入到数组最后第一个空着的单元中,数组容量加一。

2)向上筛选:与父节点比较,如果大于父节点的关键字,则与父节点交换。依次重复上述动作,直到父节点的关键字大于目标节点为止。

\

\

\

如上图:在11处插入新节点38,与父节点26比较,38>26,两者交换;38继续与父节点36比较,38>36,两者交换;38继续与父节点90比较,38<90,插入结束。

注意:

\

\

换位1中每次换位需要3次复制,两次换位需要6次复制;而换位2中先将目标节点暂存,父节点覆盖子节点,最后暂存的节点覆盖空余的节点,一共4次复制。

故需要在向上筛选过程中采用第二种换位操作。

具体代码如下:

	//插入操作
	public boolean insert(int value) {
		if (currentSize == maxSize) 
			return false;
		
		HeapNode node = new HeapNode(value);
		heapArray[currentSize] = node;
		trickleUp(currentSize++);
		return true;
	} 
	
        //向上筛选
	private void trickleUp(int index) {
		HeapNode tmpNode = heapArray[index];
		//得到目标节点父节点的索引值
		int parentIndex = (index - 1)/2;
		while (parentIndex >= 0 && index > 0) {
			//缓存节点的值大于父节点的值,才会进行后续操作,否则直接跳出
			if (tmpNode.getValue() < heapArray[parentIndex].getValue()) 
				break;
			
			heapArray[index] = heapArray[parentIndex];
			index = parentIndex;
			parentIndex = (index - 1)/2;
		}
		heapArray[index] = tmpNode;
	}

4、删除操作

1)移走根节点。

2)把最后一个节点移动到根的位置上。

3)一直向下筛选这个节点,在两个孩子中找到最大值,如果小于最大值,两者交换,直到大于它的子节点小于它的父节点为止。

\

\

\

删除代码如下:

public HeapNode remove() {
		HeapNode root = heapArray[0];
		heapArray[0] = heapArray[--currentSize];
		trickleDown(0);
		return root;
	}
	
//向下筛选
	private void trickleDown(int index) {
		if (index >= currentSize || index < 0) 
			return ;
		
		HeapNode tmpNode = heapArray[index];
		while (index < currentSize/2) {
			int leftChildIndex = 2*index + 1;
			int rightChildIndex = leftChildIndex + 1;
			
			//在左右子数中找到最大的那个
			int largeChildIndex = 0;
			if (rightChildIndex < currentSize && heapArray[leftChildIndex].getValue() < heapArray[rightChildIndex].getValue()) {
				largeChildIndex = rightChildIndex;
			} else {
				largeChildIndex = leftChildIndex;
			}
			
			//只有目标节点比孩子节点小才满足交换,否则直接跳出
			if (tmpNode.getValue() > heapArray[largeChildIndex].getValue()) {
				break;
			} else {
				heapArray[index] = heapArray[largeChildIndex];
				index = largeChildIndex;
			}
		}
		heapArray[index] = tmpNode;
	}
5、整体代码如下:
public class BinaryHeapDemo {
	public static void main(String[] args) {
		BinaryHeap bh = new BinaryHeap(50);
		bh.insert(2);
		bh.insert(7);
		bh.insert(26);
		bh.insert(25);
		bh.insert(19);
		bh.insert(17);
		bh.insert(1);
		bh.insert(90);
		bh.insert(3);
		bh.insert(36);
		bh.display();
		bh.remove();
		bh.display();
	}
}

class HeapNode {
	private int value;
	
	HeapNode (int value) {
		this.value = value;
	}
	public int getValue() {
		return value;
	}
	
	public void setValue(int value) {
		this.value = value;
	}
}

class BinaryHeap {
	private HeapNode[] heapArray = null;
	int maxSize;
	int currentSize;
	
	BinaryHeap(int maxSize) {
		this.maxSize = maxSize;
		heapArray = new HeapNode[this.maxSize];
		currentSize = 0;
	}
	
	public boolean insert(int value) {
		if (currentSize == maxSize) 
			return false;
		
		HeapNode node = new HeapNode(value);
		heapArray[currentSize] = node;
		trickleUp(currentSize++);
		return true;
	} 
	
    //向上筛选
	private void trickleUp(int index) {
		HeapNode tmpNode = heapArray[index];
		//得到目标节点父节点的索引值
		int parentIndex = (index - 1)/2;
		while (parentIndex >= 0 && index > 0) {
			//缓存节点的值大于父节点的值,才会进行后续操作,否则直接跳出
			if (tmpNode.getValue() < heapArray[parentIndex].getValue()) 
				break;
			
			heapArray[index] = heapArray[parentIndex];
			index = parentIndex;
			parentIndex = (index - 1)/2;
		}
		heapArray[index] = tmpNode;
	}
	
	public HeapNode remove() {
		HeapNode root = heapArray[0];
		heapArray[0] = heapArray[--currentSize];
		trickleDown(0);
		return root;
	}
	
	//向下筛选
	private void trickleDown(int index) {
		if (index >= currentSize || index < 0) 
			return ;
		
		HeapNode tmpNode = heapArray[index];
		while (index < currentSize/2) {
			int leftChildIndex = 2*index + 1;
			int rightChildIndex = leftChildIndex + 1;
			
			//在左右子数中找到最大的那个
			int largeChildIndex = 0;
			if (rightChildIndex < currentSize && heapArray[leftChildIndex].getValue() < heapArray[rightChildIndex].getValue()) {
				largeChildIndex = rightChildIndex;
			} else {
				largeChildIndex = leftChildIndex;
			}
			
			//只有目标节点比孩子节点小才满足交换,否则直接跳出
			if (tmpNode.getValue() > heapArray[largeChildIndex].getValue()) {
				break;
			} else {
				heapArray[index] = heapArray[largeChildIndex];
				index = largeChildIndex;
			}
		}
		heapArray[index] = tmpNode;
	}
	
	
	public void display() {
		System.out.print("heapArray:");
		for (int i = 0; i < currentSize; ++i) {
			System.out.print(heapArray[i].getValue() + " ");
		}
		System.out.println();
		System.out.println("========================================");
		
		int nBlanks = 32;
		int itemsPerRow = 1;
		int column = 0;
		int j = 0;
		while (currentSize > 0) {
			if (column == 0) {
				for (int i = 0; i < nBlanks; ++i) {
					System.out.print(" ");
				}
			}
			System.out.print(heapArray[j].getValue());
			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========================================");
	}
}
测试结果如下

 

heapArray:90 36 17 25 26 7 1 2 3 19
========================================
90
36 17
25 26 7 1
2 3 19
========================================
heapArray:36 26 17 25 19 7 1 2 3
========================================
36
26 17
25 19 7 1
2 3
========================================

二、堆排序

对一个无序数组,堆排序的思想就是使用insert()在堆中插入全部无序的数据项,然后重复的使用remove(),直到堆内无数据。

 

for (int i = 0; i < currentSize; ++i) {
    insert(a[i]);
}
for (int i = 0; i < currentSize; ++i) {
    HeapNode node = remove();
    node.getValue();
}
但可以通过两点来优化堆排序:

 

1、向下筛选到适合的位置

从一个无序的数组建堆的过程就是反复使用trickleUp()函数N次,但是此过程可以使用trickleDown()函数N/2次即可完成。

\

堆中存在诸多叶子节点,这些叶子节点因为没有子节点所以没有违背堆的条件(大于子节点的关键字),因此不用对这些节点进行trickleDown()操作。可以从最后一个有子节点的节点开始依次向下筛选,进行trickleDown()操作直到根节点位置。那最后一个有子节点的节点索引是多少呢?若最后一个叶子节点的索引为index,则父节点便是最后一个有子节点的节点,索引为(index-1)/2=(currentSize-1-1)/2=currentSize/2-1。

从一个无序数组建堆的代码如下:

 

//将一个无序数组建堆就是从最后一个有子节点的节点开始,依次向下筛选
	public void buildHeap() {
		for (int i = currentSize/2 - 1; i >= 0; --i) {
			trickleDown(i);
		}
	}
2、使用同一个数组

 

堆排序的过程需要两个大小为N的数组:初始数组和用于堆的数组。事实上堆和初始数组可以用同一个数组。当执行remove()操作后,堆内的节点数减一,数组最后的位置便空了出来,这时此位置可以存储移除的节点。

\

代码如下:

 

	private void insertAt(int index, HeapNode node) {
		if (index < 0 || index >= maxSize)
			return ;
		
		heapArray[index] = node;
	}
	
	public void heapSort() {
		for (int i = currentSize-1; i > 0; --i) {
			HeapNode node = remove();
			insertAt(i, node);
		}
	}

堆排序完整代码如下:

 

 

public class HeapSortDemo {
	public static void main(String[] args) {
		HeapSort hs = new HeapSort(30);
		hs.buildRandomArray();
		hs.display();
		hs.buildHeap();
		hs.display();
		hs.heapSort();
		hs.displayArray();
	}
}

class HeapSort {
	private HeapNode[] heapArray = null;
	private int maxSize;
	private int currentSize;
	
	HeapSort(int maxSize) {
		this.maxSize = maxSize;
		heapArray = new HeapNode[this.maxSize];
		currentSize = 0;
	}
	
	private HeapNode remove() {
		HeapNode root = heapArray[0];
		heapArray[0] = heapArray[--currentSize];
		trickleDown(0);
		return root;
	}
	
	private void trickleDown(int index) {
		if (index >= currentSize || index < 0) 
			return ;
		
		HeapNode tmpNode = heapArray[index];
		while (index < currentSize/2) {
			int leftChildIndex = 2*index + 1;
			int rightChildIndex = leftChildIndex + 1;
			
			//在左右子数中找到最大的那个
			int largeChildIndex = 0;
			if (rightChildIndex < currentSize && heapArray[leftChildIndex].getValue() < heapArray[rightChildIndex].getValue()) {
				largeChildIndex = rightChildIndex;
			} else {
				largeChildIndex = leftChildIndex;
			}
			
			//只有目标节点比孩子节点小才满足交换,否则直接跳出
			if (tmpNode.getValue() > heapArray[largeChildIndex].getValue())
				break;
			
			heapArray[index] = heapArray[largeChildIndex];
			index = largeChildIndex;
		}
		heapArray[index] = tmpNode;
	}
	
	//将一个无序数组建堆就是从最后一个有子节点的节点开始,依次向下筛选
	public void buildHeap() {
		for (int i = currentSize/2 - 1; i >= 0; --i) {
			trickleDown(i);
		}
	}
	
	private void insertAt(int index, HeapNode node) {
		if (index < 0 || index >= maxSize)
			return ;
		
		heapArray[index] = node;
	}
	
	//生成一个无序的数组
	public void buildRandomArray() {
		for (int i = 0; i < maxSize; ++i) {
			int randomValue = (int)(Math.random()*100);
			HeapNode node = new HeapNode(randomValue);
			insertAt(currentSize++, node);
		}
	}
	
	public void heapSort() {
		for (int i = currentSize-1; i > 0; --i) {
			HeapNode node = remove();
			insertAt(i, node);
//			System.out.println("insert:" + i + "-" + heapArray[i].getValue());
		}
	}
	
	public void displayArray() {
		System.out.print("heapArray:");
		for (int i = 0; i < maxSize; ++i) {
			System.out.print(heapArray[i].getValue() + " ");
		}
		System.out.println();
	}
	
	public void display() {
		displayArray();
		System.out.println("========================================");
		
		int nBlanks = 32;
		int itemsPerRow = 1;
		int column = 0;
		int j = 0;
		while (currentSize > 0) {
			if (column == 0) {
				for (int i = 0; i < nBlanks; ++i) {
					System.out.print(" ");
				}
			}
			System.out.print(heapArray[j].getValue());
			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========================================");
	}
}
测试结果如下:

 

heapArray:9 25 40 86 74 14 44 82 68 49 55 68 11 4 51 63 79 85 1 72 29 64 95 45 38 57 77 57 92 24
========================================
9
25 40
86 74 14 44
82 68 49 55 68 11 4 51
63 79 85 1 72 29 64 95 45 38 57 77 57 92 24
========================================
heapArray:95 86 92 85 74 77 57 82 68 72 64 68 57 44 51 63 79 9 1 49 29 25 55 45 38 14 11 40 4 24
========================================
95
86 92
85 74 77 57
82 68 72 64 68 57 44 51
63 79 9 1 49 29 25 55 45 38 14 11 40 4 24
========================================
heapArray:1 4 9 11 14 24 25 29 38 40 44 45 49 51 55 57 57 63 64 68 68 72 74 77 79 82 85 86 92 95
三、效率
堆排序在最好与最快的情况下时间复杂度都是O(nlogn),空间复杂度为O(1)

堆排序是一种不稳定的排序

点击复制链接 与好友分享!回本站首页
相关TAG标签
上一篇:Spring In Action 01 ---装配Bean
下一篇:Spring核心概念总结
相关文章
图文推荐
文章
推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站