文档章节

数据结构之堆排序

润群
 润群
发布于 2016/02/01 22:49
字数 506
阅读 88
收藏 2
点赞 1
评论 0

秉承着对知识的渴望,以及对计算机那种强烈的好奇心。。在完成MOOC大学翁凯老师的的c语言课程后,继续探索陈越姥姥的数据结构。在此,灰常感谢MOOC这个平台,让我这个高三肆业狗能够系统的学习计算机课程(sorry,有点偏题了~~~~)

 

上班时间有时挺忙的,但是一有时间我都会进行自身知识的补充。。。

正好过年放假了,可以把剩下的排序算法学习完~~~~想想就有点激动。。。。

这一次是对一个数组进行堆排序。。。

大体思路是循环把数组调整成最大堆,然后把第一个元素放到末尾,接着将数组长度减1,直到循环结束。

本来觉得是一个很简单的算法,结果实现起来不断的报segmentation fault(当时第一反应就是数组越界了~~)。。。。

而sbulime text下c的错误调试又不熟(printf竟然都不输出了!!!!好郁闷)

只好打开terminal进行调试。。。。

果然,就是数组越界引起的。。。

最后,记录下自己的核心代码。(嗯,以自己共勉。。)

  

堆排序的算法部分:

void heap_sort(int arr[], int length){
	for (int i = length; i > 0; i--)
	{
		// build max heap....
		change_array_to_max_heap(i, arr);
		// put max element to tail...
		int temp = arr[i-1];
		arr[i-1]=arr[0];
		arr[0]=temp;
	}
		
}

 

建堆堆算法部分:

void change_array_to_max_heap(int array_size, int element[]){
	// element[0] = 0;
	// ao~~~~~~~ decreasing by step 2,for comparing the minimum heap....
	for (int i = array_size; i/2>=0; i-=2)
	{
		int min_top_heap_index = i/2;
		if (min_top_heap_index == 0 ) min_top_heap_index = 1;
		// comparing the current and the sub heap...
		for (int top_index = min_top_heap_index; top_index <= array_size; top_index*=2)
		{
			int child_left = top_index*2;
			if(child_left > array_size ) break;
			// if right element greater than left ....
			if(child_left+1<=array_size && 
				element[child_left]>element[child_left-1]){
				child_left++;
			}
			
			// if parent less than child....
			if(element[child_left-1] > element[top_index-1]){
				// printf("child:%d,top_index:%d,child_val:%d,top_val:%d\n", child_left,top_index,element[child_left-1],element[top_index-1]);
				// exchange position.....
				int temp = element[child_left-1];
				element[child_left-1] = element[top_index-1];
				element[top_index-1] = temp;
			}
		}
	}
}

 

 

好吧,顺便放上github的链接(哈哈,广告插入

heap struct

 

© 著作权归作者所有

共有 人打赏支持
润群
粉丝 0
博文 7
码字总数 2837
作品 0
深圳
程序员
常用数据结构以及数据结构的排序算法

数组 (Array)   在程序设计中,为了处理方便, 把具有相同类型的若干变量按有序的形式组织起来。这些按序排列的同类数据元素的集合称为数组。在C语言中, 数组属于构造数据类型。一个数组可...

带梦想一7飞
2012/09/13
0
0
排序----堆排序

上一篇:快速排序 数据结构--堆的构造和实现 堆排序可以分为两个阶段: 构造堆。将原始数组重新组织安排进一个堆中 下沉排序。从堆中按递减顺序取出所有元素并得到排序结果 用下沉操作由N个元...

Superheros
2017/11/30
5
0
深入浅出 PHP SPL(PHP 标准库)

一、什么是spl库? SPL是用于解决典型问题(standard problems)的一组接口与类的集合。 此扩展只能在php 5.0以后使用,从PHP 5.3.0 不再被关闭,会一直有效.成为php内核组件一部份。 SPL提供了...

NateHuang
06/08
0
0
白话经典算法系列之七 堆与堆排序

堆排序与快速排序,归并排序一样都是时间复杂度为O(N*logN)的几种常见排序方法。学习堆排序前,先讲解下什么是数据结构中的二叉堆。 二叉堆的定义 二叉堆是完全二叉树或者是近似完全二叉树。...

长平狐
2012/12/10
83
0
白话经典算法系列之七 堆与堆排序

堆排序与快速排序,归并排序一样都是时间复杂度为O(N*logN)的几种常见排序方法。学习堆排序前,先讲解下什么是数据结构中的二叉堆。 二叉堆的定义 二叉堆是完全二叉树或者是近似完全二叉树。...

彭博
2012/04/12
190
0
基于堆实现的优先级队列:PriorityQueue 解决 Top K 问题

1、认识 PriorityQueue PriorityQueue是从JDK1.5开始提供的新的数据结构接口,它是一种基于优先级堆的极大优先级队列。优先级队列是不同于先进先出队列的另一种队列。每次从队列中取出的是具...

大数据之路
2013/06/02
0
0
PHP-利用二叉堆实现TopK-算法

介绍 在以往工作或者面试的时候常会碰到一个问题,如何实现海量TopN,就是在一个非常大的结果集里面快速找到最大的前10或前100个数,同时要保证内存和速度的效率,我们可能第一个想法就是利用...

简单方式
2017/04/23
0
0
JavaScript数据结构与算法(堆)

堆是一种完全二叉树. 堆得使用基本是通过最大堆和最小堆来实现的! 最大堆,最大堆中的最大元素值出现在根结点(堆顶),堆中每个父节点的元素值都大于等于其孩子结点 最小堆,最小堆中的最大元...

fiveoneLei
07/12
0
0
堆与堆排序

堆排序与快速排序,归并排序一样都是时间复杂度为O(N*logN)的几种常见排序方法。学习堆排序前,先讲解下什么是数据结构中的二叉堆。 二叉堆的定义 二叉堆是完全二叉树或者是近似完全二叉树。...

长平狐
2012/10/08
160
0
算法-数据结构

时间复杂度 O(log n) 意味着什么? 写给小白的时间复杂度指南 查找算法的 Java 实现 查找算法的 Java 实现 两个有序数组合并成一个有序数组 用拉链法和线性探测法解决哈希冲突 用拉链法和线性...

掘金官方
2017/12/14
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

用Python绘制红楼梦词云图,竟然发现了这个!

Python在数据分析中越来越受欢迎,已经达到了统计学家对R的喜爱程度,Python的拥护者们当然不会落后于R,开发了一个个好玩的数据分析工具,下面我们来看看如何使用Python,来读红楼梦,绘制小...

猫咪编程
16分钟前
0
0
Java中 发出请求获取别人的数据(阿里云 查询IP归属地)

1.效果 调用阿里云的接口 去定位IP地址 2. 代码 /** * 1. Java中远程调用方法 * http://localhost:8080/mavenssm20180519/invokingUrl.action * @Title: invokingUrl * @Description: * @ret......

Lucky_Me
39分钟前
1
0
protobuf学习笔记

相关文档 Protocol buffers(protobuf)入门简介及性能分析 Protobuf学习 - 入门

OSC_fly
昨天
0
0
Mybaties入门介绍

Mybaties和Hibernate是我们在Java开发中应用的比较多的两个ORM框架。当然,目前Mybaties正在慢慢取代Hibernate,这是因为相比较Hibernate而言Mybaties性能更好,响应更快,更加灵活。我们在开...

王子城
昨天
2
0
编程学习笔记之python深入之装饰器案例及说明文档[图]

编程学习笔记之python深入之装饰器案例及说明文档[图] 装饰器即在不对一个函数体进行任何修改,以及不改变整体的原本意思的情况下,增加函数功能的新函数,因为这个新函数对旧函数进行了装饰...

原创小博客
昨天
0
0
流利阅读笔记33-20180722待学习

黑暗中的生物:利用奇技淫巧快活生存 Daniel 2018-07-22 1.今日导读 如果让你在伸手不见五指的黑暗当中生存,你能熬过几天呢?而大千世界,无奇不有。在很多你不知道的角落,有些生物在完全黑...

aibinxiao
昨天
6
0
Hystrix降级逻辑中如何获取触发的异常

通过之前Spring Cloud系列教程中的《Spring Cloud构建微服务架构:服务容错保护(Hystrix服务降级)》一文,我们已经知道如何通过Hystrix来保护自己的服务不被外部依赖方拖垮的情况。但是实际...

程序猿DD
昨天
1
0
gin endless 热重启

r := gin.New()r.GET("/", func(c *gin.Context) {c.String(200, config.Config.Server.AppId)})s := endless.NewServer(":8080", r)s.BeforeBegin = func(add string) ......

李琼涛
昨天
1
0
JAVA模式之代理模式

平时一直在用spring,spring中最大的特效IOC和AOP,其中AOP使用的就是代理模式.闲着无聊,随手写了一个代理模式,也记录下代理模式的实现Demo. 比如现在有一个场景是:客户想要增加一个新的功能,...

勤奋的蚂蚁
昨天
0
0
ES15-JAVA API 索引管理

1.创建连接 创建连接demo package com.sean.esapi.client;import java.net.InetSocketAddress;import org.elasticsearch.action.get.GetResponse;import org.elasticsearch.clien......

贾峰uk
昨天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部