首页 / 算法 / 算法导论(1)堆排序
算法导论(1)堆排序
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了算法导论(1)堆排序,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1990字,纯文字阅读大概需要3分钟。
内容图文
#pragma once #include<iostream> using namespace std; /*返回节点i的父结点*/ int Parent(int i) { if (i <= 0) return -1; else return (i - 1) / 2; } /*返回节点i的左孩子*/ int Left(int i) { return 2 * i + 1; } /*返回结点i的右孩子*/ int Right(int i) { return 2 * i+2; } /*交换两个数*/ template<class T> void Swamp(T &a, T &b) { T temp; temp = a; a = b; b = temp; } /*维护最大堆的性质 inputData为输入的数组 rootNode为根节点,该函数使以rootNode为根的一个子树,满足最大堆的性质 heapSize为堆的尺寸大小,heapSize不一定等于inputData的数据长度*/ template<class T> void MaxHeap(T* inputData, int rootNode, int heapSize) { int left = Left(rootNode); int right = Right(rootNode); int largest; if (left<heapSize &&inputData[left]>inputData[rootNode]) largest = left; else largest = rootNode; if (right<heapSize&&inputData[right]>inputData[largest]) largest = right; if (largest != rootNode) { Swamp(inputData[rootNode], inputData[largest]); MaxHeap(inputData, largest, heapSize); } } /* 构建最大堆 dataLength为输入数组的长度 */ template<class T> void BuildMaxHeap(T* inputData, int dataLength) { int parentNode = (dataLength - 2) / 2; //完全二叉树的所有的根节点 int heapSize = dataLength; for (int i = parentNode; i >= 0; i--) { MaxHeap(inputData, i, heapSize); } } /* 堆排序算法 */ template<class T> void HeapSort(T* inputData, int dataLength) { int heapSize = dataLength; BuildMaxHeap(inputData, dataLength); //构建一个最大堆 //cout << "最大堆为:"; //for (int i = 0; i < dataLength; i++) { // cout << inputData[i] << " "; //} //cout << endl; //最大堆的最大元素均为inputData[0] for (int i = dataLength - 1; i > 0; i--) { //将最大的元素放在数组的最末位置,次末位置,……,依次递减直到1 Swamp(inputData[0], inputData[i]); //使堆的大小减一,用以忽略已经排好的后面的最大元素 heapSize--; //由于根节点0不满足最大堆的性质了(别的根节点仍满足最大堆性质),所以再次调用MaxHeap让其成为最大堆 MaxHeap(inputData, 0, heapSize); //cout << "i="<<i<<",最大堆为:"; //for (int i = 0; i < dataLength; i++) { // cout << inputData[i] << " "; //} //cout << endl; } }
原文:http://www.cnblogs.com/ql698214/p/5424300.html
内容总结
以上是互联网集市为您收集整理的算法导论(1)堆排序全部内容,希望文章能够帮你解决算法导论(1)堆排序所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。