完全二叉树:
1、除最后一层外,其他层结点数应该达到最大值。2、最后一层结点都连续集中在左侧
二叉堆:
1、二叉堆是一颗完全二叉树
2、最大堆:父结点的值总是不小于任何一个子结点的值
3、最小堆:父结点的值总是不大于任何子结点的值
创建一个二叉最大t堆
usintg System; using System.Collections.Generic; using System.Text; namespace 排序算法 { class MaxHeap<E> where E :IComparable<E> { private E[] heap; private int N; public MaxHeap(int capacity) { heap = new E[capacity + 1]; N = 0; } public MaxHeap() : this(10) { } public int Count { get { return N; } } public bool IsEmpty { get { return N == 0; } } //插入一个元素 public void Insert(E e) { if( N == (heap.Length - 1)) { ResetCapacity( heap.Length* 2 ); } heap[N + 1] = e; N++; Swim(N); } public E RemoveMax() { Swap(1, N); E max = heap[N]; heap[N] = default(E); N--; Sink(1); if(N == (heap.Length - 1) / 4) { ResetCapacity(heap.Length / 2); } return max; } public E Max() { if (IsEmpty) { throw new ArithmeticException("堆为空!"); } else { return heap[1]; } } //下沉操作 private void Sink(int k) { while (2 * k <= N) { int j = 2 * k; if (j + 1 <= N && heap[j + 1].CompareTo(heap[j]) > 0) { j++; } if(heap[k].CompareTo(heap[j]) >= 0) { break; } Swap(k, j); k = j; } } //元素上游 private void Swim(int k) { while(k > 1 && heap[k].CompareTo(heap[k /2]) > 0) { Swap(k, k / 2); k = k / 2; } } private void Swap(int i, int j) { E e = heap[i]; heap[i] = heap[j]; heap[j] = e; } private void ResetCapacity(int newCapacity) { E[] newHeap = new E[newCapacity]; for(int i = 1; i <= N; i++) { newHeap[i] = heap[i]; } heap = newHeap; } public override string ToString() { StringBuilder res = new StringBuilder(); res.Append("["); for(int i = 1; i<=N; i++) { res.Append(heap[i]); if(i != N) { res.Append(" ,"); } } res.Append("]"); return res.ToString(); } } }
创建一个最小堆:
using System; using System.Collections.Generic; using System.Text; namespace 排序算法 { class MinHeap<E> where E : IComparable<E> { private E[] heap; private int N; public MinHeap(int capacity) { heap = new E[capacity + 1]; N = 0; } public MinHeap() : this(10) { } public int Count { get { return N; } } public bool IsEmpty { get { return N == 0; } } //插入一个元素 public void Insert(E e) { if (N == (heap.Length - 1)) { ResetCapacity(heap.Length * 2); } heap[N + 1] = e; N++; Swim(N); } public E RemoveMin() { Swap(1, N); E min = heap[N]; heap[N] = default(E); N--; Sink(1); if (N == (heap.Length - 1) / 4) { ResetCapacity(heap.Length / 2); } return min; } public E Min() { if (IsEmpty) { throw new ArithmeticException("堆为空!"); } else { return heap[1]; } } //下沉操作 private void Sink(int k) { while (2 * k <= N) { int j = 2 * k; if (j + 1 <= N && heap[j + 1].CompareTo(heap[j]) < 0) { j++; } if (heap[k].CompareTo(heap[j]) <= 0) { break; } Swap(k, j); k = j; } } //元素上游 private void Swim(int k) { while (k > 1 && heap[k].CompareTo(heap[k / 2]) < 0) { Swap(k, k / 2); k = k / 2; } } private void Swap(int i, int j) { E e = heap[i]; heap[i] = heap[j]; heap[j] = e; } private void ResetCapacity(int newCapacity) { E[] newHeap = new E[newCapacity]; for (int i = 1; i <= N; i++) { newHeap[i] = heap[i]; } heap = newHeap; } public override string ToString() { StringBuilder res = new StringBuilder(); res.Append("["); for (int i = 1; i <= N; i++) { res.Append(heap[i]); if (i != N) { res.Append(" ,"); } } res.Append("]"); return res.ToString(); } } }
堆排序:
namespace 排序算法 { // 时间复杂度O(n) class HeapSort1 { public static void Sort(int[] arr) { int n = arr.Length; MaxHeap<int> maxHeap = new MaxHeap<int>(); for(int i = 0; i < n, i++) { maxHeap.Insert(arr[i]); } for(int i = n -1; i >= 0; i--) { arr[i] = maxHeap.RemoveMax(); } } } }
上面堆排序的时间复杂度是O(n)
下面是用原地堆排序时间复杂度是O(logn)
namespace 排序算法 { // 时间复杂度O(n) class HeapSort1 { public static void Sort(int[] arr) { int n = arr.Length; MaxHeap<int> maxHeap = new MaxHeap<int>(); for(int i = 0; i < n, i++) { maxHeap.Insert(arr[i]); } for(int i = n -1; i >= 0; i--) { arr[i] = maxHeap.RemoveMax(); } } } }
最大堆队列
using System; using System.Collections.Generic; using System.Collections.Immutable; using System.Runtime.CompilerServices; using System.Text; namespace 排序算法 { //最大优先队列 class MaxPQ<E> : IQueue<E> where E : IComparable<E> { private MaxHeap<E> heap; public MaxPQ(int capacity) { heap = new MaxHeap<E>(capacity); } public MaxPQ() { heap = new MaxHeap<E>(); } public int Count { get {return heap.Count; } } public bool isEmpty { get { return heap.IsEmpty; } } public E Dequeue() { return heap.RemoveMax(); } public void Enqueue(E e) { heap.Insert(e); } public E Peek() { return heap.Max(); } public override string ToString() { return heap.ToString(); } } }
最小堆队列:
using System; using System.Collections.Generic; using System.Collections.Immutable; using System.Runtime.CompilerServices; using System.Text; namespace 排序算法 { //最大优先队列 class MinPQ<E> : IQueue<E> where E : IComparable<E> { private MinHeap<E> heap; public MinPQ(int capacity) { heap = new MaxHeap<E>(capacity); } public MinPQ() { heap = new MaxHeap<E>(); } public int Count { get {return heap.Count; } } public bool isEmpty { get { return heap.IsEmpty; } } public E Dequeue() { return heap.RemoveMin(); } public void Enqueue(E e) { heap.Insert(e); } public E Peek() { return heap.Min(); } public override string ToString() { return heap.ToString(); } } }
优先对列使用场景:可以动态处理数据。