package com.chenrong.other;
/**
* @author ChenRong
* @description: 实现简单的大根堆, 元素从大往小排序
* @date 2020/4/9 21:08
*/
public class BigHeap {
// 记录堆内元素的个数,同时下一空元素下标
private Integer count = 0;
// 最多装100个元素
private Integer[] arr = new Integer[100];
/**
* @Description 返回大根堆里面的元素个数
* @param
* @Return java.lang.Integer
* @Author ChenRong
* @Date 2020/4/9 21:13
**/
public Integer size(){
return count;
}
/**
* @Description 往堆里面添加元素
* @param num
* @Return java.lang.Integer
* @Author ChenRong
* @Date 2020/4/9 21:34
**/
public Integer put(Integer num) throws Exception{
if( count >= 100){
throw new Exception("大堆的元素个数已经达到100上限");
}
arr[count++] = num;
// 上浮,最后一个元素的下标为 count - 1
ShiftUp(arr, count - 1);
return num;
}
/**
* @Description 清除大根堆 根部的元素
* @param
* @Return java.lang.Integer
* @Author ChenRong
* @Date 2020/4/9 21:35
**/
public Integer remove() throws Exception{
if(count == 0){
throw new Exception("大堆没有任何元素");
}
Integer num = arr[0];
// 首尾交换
swap(arr, 0, count - 1);
// 下一空元素的下标减少1
count--;
// 下沉, 从根元素开始
ShiftDown(arr, 0);
return num;
}
/**
* @Description 添加的元素上浮
* @param arr
* @param index 当前元素的下标
* @Return void
* @Author ChenRong
* @Date 2020/4/9 21:32
**/
private void ShiftUp(Integer[] arr, Integer index){
Integer parent = (index - 1) / 2;
// 当前节点不是根节点
if (index > 0){
if(arr[parent] < arr[index]){
swap(arr, parent, index);
ShiftUp(arr, parent);
}
}
}
/**
* @Description 元素下沉
* @param arr
* @param index 当前元素的下标
* @Return void
* @Author ChenRong
* @Date 2020/4/9 21:32
**/
private void ShiftDown(Integer[] arr, Integer index){
// 左孩子节点
Integer leftChild = index*2 + 1;
// 右孩子节点
Integer rightChild = index*2 + 2;
// 不存在孩子节点
if(count <= leftChild){
return ;
}
if(count <= rightChild){ // 仅有左孩子
if(arr[index] < arr[leftChild]){
swap(arr, index, leftChild);
ShiftDown(arr, leftChild);
}
}else{ // 有左右孩子
// 记录最大孩子的下标
Integer temp = 0;
temp = arr[leftChild] > arr[rightChild] ? leftChild : rightChild;
if(arr[index] < arr[temp]){
swap(arr, index, temp);
ShiftDown(arr, temp);
}
}
}
/**
* @Description 元素的交换
* @param arr
* @param i
* @param j
* @Return void
* @Author ChenRong
* @Date 2020/4/9 22:06
**/
private void swap(Integer[] arr, Integer i, Integer j){
Integer temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String[] args) throws Exception {
BigHeap heap = new BigHeap();
Integer[] arr = new Integer[]{1, -1, 5, 9, 8, -5, 7, 123, -19};
for(Integer num : arr){
heap.put(num);
}
System.out.println("元素的个数为: " + heap.size());
System.out.println("原来元素的情况:");
for(Integer num : arr){
System.out.print(num + " ");
}
System.out.println("\n");
System.out.println("排序后元素的情况:");
while (heap.size() != 0){
System.out.print(heap.remove() + " ");
}
}
}