首页 > 代码库 > 数据结构中的堆
数据结构中的堆
一：堆排序
堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值，即A[PARENT[i]] >= A[i]。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。下面附上简单C#简单实现：
using System;using System.Collections.Generic;using System.Linq;using System.Text;using System.Threading.Tasks;namespace Heap{ /// <summary> /// 堆排序实现 /// </summary> class HeapSort { public static void Sort<T>(T[] originArr) where T : IComparable { //首先建堆 BuildMaxHeap<T>(originArr); //在一个堆上在进行排序 RealSort<T>(originArr); } private static void RealSort<T>(T[] originArr) where T : IComparable { for (int i = 0; i < originArr.Length-1; i++) { Swap<T>(originArr , 0, originArr.Length - (i+1)); MaxHeapIFY<T>(originArr, originArr.Length - (i + 1), 0); } } /// <summary> /// 1.首先是需要清楚 GetMaxObjInHeap方法的作用，是在一个堆上插入一个值，并保证插入后堆的性质不变 /// 2.堆其实是满足完全二叉树的性质的，也就是 叶子节点 = （总结点+1）/2 或者 总结点 / 2 /// 3.把每个叶子节点看做一个独立的最大堆，自底而上构建最大堆 /// </summary> private static void BuildMaxHeap<T>(T[] originArr) where T : IComparable { int len = originArr.Length / 2; for (int i = len; i >= 0 ; i--) { MaxHeapIFY<T>(originArr,originArr.Length, i); } } /// <summary> /// 堆操作中核心方法，并维护最大堆的性质 /// 假设originList是一个最大堆，实现在堆固定位置插入元素，并同时保证最大堆的性质 /// </summary> private static void MaxHeapIFY<T>(T[] originList, int heapSie, int pos) where T : IComparable { int len = heapSie; int largest = 0; int cLeft = pos * 2; int cRight = pos * 2 + 1; while (cLeft < len || cRight < len) { largest = cLeft; if (cRight < len && originList[cLeft].CompareTo(originList[cRight]) < 0) { largest = cRight; } if (originList[pos].CompareTo(originList[largest]) >= 0) { break; } else { Swap<T>(originList, pos, largest); pos = largest; cLeft = pos * 2; cRight = pos * 2 + 1; } } } /// <summary> /// 数组中两个元素交换 /// </summary> private static void Swap<T>(T[] originList, int posFirst, int posSec) where T : IComparable { T temp = originList[posFirst]; originList[posFirst] = originList[posSec]; originList[posSec] = temp; } public static void PrintArr<T>(T[] arr) { for (int i = 0; i < arr.Length; i++) { Console.Write(arr[i] + " , "); } Console.WriteLine(""); Console.WriteLine("=================="); } }}
数据结构中的堆
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。