1 2/* 3 * Copyright 2006 The Android Open Source Project 4 * 5 * Use of this source code is governed by a BSD-style license that can be 6 * found in the LICENSE file. 7 */ 8 9 10#ifndef SkTSort_DEFINED 11#define SkTSort_DEFINED 12 13#include "SkTypes.h" 14 15template <typename T> 16void SkTHeapSort_SiftDown(T array[], int root, int bottom) { 17 while (root*2 + 1 <= bottom) { 18 int child = root * 2 + 1; 19 if (child+1 <= bottom && array[child] < array[child+1]) { 20 child += 1; 21 } 22 if (array[root] < array[child]) { 23 SkTSwap<T>(array[root], array[child]); 24 root = child; 25 } else { 26 break; 27 } 28 } 29} 30 31template <typename T> void SkTHeapSort(T array[], int count) { 32 int i; 33 for (i = count/2 - 1; i >= 0; --i) { 34 SkTHeapSort_SiftDown<T>(array, i, count-1); 35 } 36 for (i = count - 1; i > 0; --i) { 37 SkTSwap<T>(array[0], array[i]); 38 SkTHeapSort_SiftDown<T>(array, 0, i-1); 39 } 40} 41 42#endif 43