text:
Talk:Heapsort

Worst case performance
The worst case performance is currently listed as O((n log n)^n), I believe this may be error and I going to change it to O(n log n). If anyone wants to explain why I am wrong, please do so here. In fact looking at the rest of the article, which lists the worst case as O(n log n) several times, I think that the previous worst case was either typo or vandalism. -Uselesswarrior (talk) 17:28, 2 March 2009 (UTC)

C-code
The example C-code was tested and found to be flawed (Obviously, since in the heapify routine, it says start=count%2 instead of count/2). The following test vector {2,5,3,4,1} returned {1,2,4,3,5}. Many other failing examples have been found. The problem seems to be in the build heap portion of the code, which sometimes fails to create a valid max-heap. When the sift_in function is replaced with a simpler sift_down function for building the heap, the code works.

Also, the comments of the sift_in function seem incorrect. The function first performs a sift_down and then a sift_up, unless you are viewing the heap upside down.

—The preceding unsigned comment was added by Rekinser (talk • contribs) 21:41, 8 December 2006 (UTC).

I concur. The initial heap build does not work. The build phase examines the first half of the data, in reverse order. With other algorithms, this only affects children that are to the right of the entry being processed. Hence the max heap property is progressively made true with right to left processing of all non-leaf entries.

Where the C code fails is that its "sift_in" will affect parent nodes of the initial "free" node being processed.

A bit of horrible patching on "sift_in" does make it work:

a) Change its parameter from "free" to be "free_in"

b) Add "unsigned free = free_in;" at the start

c) Modify the "while"'s "(i=free/2)" to say "((i=free/2)>=free_in)"

MESSY! Probably not optimal. Can anyone suggest a more sensible change? Lauwr 00:06, 23 January 2007 (UTC)

The C code does not include stdlib and I realize that "free" is a descriptive variable name, but wouldn't it still be good practice not to have a variable name that could so easily be confused with the stdlib function? 85.11.196.122 07:32, 23 January 2007 (UTC)

Some time has past and the code on the page has not been corrected. I've also come into c heapsort implementation flaw. As I don't want another person to waste time (as I did) I will correct the main page with the change proposed by Lauwr. Sergio Demian Lerner. --24.232.216.146 20:39, 31 May 2007 (UTC)

This C code seems to work, it's an almost direct translation of the pseudocode on the page: void heapsort (int *, int); void heapify (int *, int); void siftdown (int *, int, int); void heapsort (int *arr, int len) { int end; int tmp; heapify (arr, len); end = len - 1; while (end > 0) { tmp = arr[0]; arr[0] = arr[end]; arr[end] = tmp; siftdown (arr, 0, --end); }       }        void heapify (int *arr, int len) { int start; for (start = len / 2 - 1; start >= 0; --start) siftdown (arr, start, len - 1); }       void siftdown (int *arr, int start, int end) { int root, child, tmp; root = start; while (root * 2 + 1 <= end) { child = root * 2 + 1; if (child < end && arr[child] < arr[child + 1]) ++child; if (arr[root] < arr[child]) { tmp = arr[root]; arr[root] = arr[child]; arr[child] = tmp; root = child; } else { return; }               }        }

Numerical Recipies copyright
Is it acceptable to use code adapted from Numerical Recipies in C? I don't own a copy, so I can't quote it, but I am led to understand that it is very restrictive in its usage licence. — PhilHibbs | talk
 * That's correct. The code can only be used on one screen if you purchase a single-screen license; distribution is prohibited. Deco 00:27, 27 Apr 2005 (UTC)

Pseudocode question
I'm fairly certain that the pseudocode in this article does not work on some arrays of odd length. That is, if length($$a$$) is odd, then occassionally heapSort($$a$$) produces an array that is one swap away from sorted. For example, heapSort([1,2,3]) -> [1,3,2] and heapSort([2,1,3,5,4]) -> [1,2,4,3,5]. If, in heapSort, I replace the line var int start := count / 2 - 1 with var int start := count / 2 it seems to correct the bug. Have I missed something? --Quaternion 22:28, 18 Feb 2005 (UTC)

Some algorithms employ data sentinels to avoid checking for array bounds. They can simplify the algorithm and also speed up execution. For heapsort, a data sentinel at the end of the array would prevent the need to check for the special case of a node having just one child, which occurs when N is odd.Gj7 13:48, 23 June 2007 (UTC)

Oops, that should have been "which occurs when N is even."Gj7 13:55, 23 June 2007 (UTC)

--
 * The pseudocode works for me. Make sure you are really using integer based variables for the value of start, or take the floor value of count/2.  For example, in perl I said   --Dustball 02:36, 4 July 2006 (UTC)
 * if you're using Java, try  (right-shift floor) 76.64.22.234 02:45, 24 May 2007 (UTC)

Is it for some reason impractical to implement a quaternary heapsort?

 * It's not impractical to implement a quaternary heapsort. In fact, I managed to implement an N-ary Heapsort algorithm in Java. — pguedes

--

i think there's a bug in the final line of the python program. should it not be called with the first element of the array, 1 instead of with 0?

To my mind O(N log N) is not approximately linear for large N, but I suppose it depends on your viewpoint. There are sort methods which are linear - e.g pigeon hole sort for a densely populated set of integers, and these could be expected to run significantly faster.

However, both heapsort and quicksort are, for most practical purposes, amongst the fastest sorts. Note that scrambling the elements before doing a quicksort is often more effective - as often the elements are almost in order, in which case quicksort is known to be slow. This does not apply to heapsort.

 * I agree with the O(N log N) statement, and eliminated the claim that it's about linear. Scrambling the elements isn't a really effective strategy for improving quicksort, since scrambling involves a lot of cache misses, making it a very slow operation. Deco 19:36, 4 Nov 2004 (UTC)

The article states that an in-place (O(1) auxiliary space) quicksort is possible. Is that true? Don't you need a stack to manage what parts of the array you still need to sort? --Ryan Stone 15:52, 4 Nov 2004 (UTC)

 * Oh, I see it now. The data stored on the stack in quicksort is the pivot positions. It is quite possible to compute, rather than store, the pivot positions, in restricted implementations — for example, in a quicksort implementation which always uses the median. I'm not aware of any fast in-place quicksort variant though. Deco 19:31, 4 Nov 2004 (UTC)

There is something I've always wondered about heapsort. When you've created the heap and starts to extract the largest element of it, you swap it with the element with the largest index in the heap to get the value in the right position (ie when you just have created the heap, the first thing you do is to swap the 1st element with the Nth, then heapify, then you swap the 1st element with the (N-1)th and heapify and so on). But if you do that you will most of a time get a very low value at the top of the heap (since the value was previously at the bottom of the heap), and since that value is pretty low the siftup will take longer. Why don't you instead implement the heap as a min-heap instead of a max-heap? Then the head would be at the right position directly (no need to swap) and you could make one of it's children (the element just after it) the head and then heapify. The heapifying would take shorter time on average wouldn't it? I mean, it obvoiusly wouldn't be asymptotically faster, but it would be faster, n'est pas? Gkhan 01:21, Feb 14, 2005 (UTC)
 * And oh yeah, I realize that the talk-page isn't really the right forum for asking techincal questions, but indulge me Gkhan 01:22, Feb 14, 2005 (UTC)

 * Note: I removed my previous answer here -- I had the algorithm Gkhan was describing completely wrong
 * Put briefly, the algorithm you describe isn't very effective at all -- assymptotically it's worse than Bubble sort. Actually, what you describe is an expensive version of Selection sort.
 * Here's the reason why it's so poor: The heapifying operation takes O(n log n). What you're suggesting is that we heapify n elements, then n - 1 elements, ... until finally heapifying an array with 1 element(ok, we could skip that, but it doesn't make too much of a difference, and does make the calculations below easier.
 * The number of operations we do will thus be O(n log n) + O ( (n - 1) log (n - 1) ) + ... + O ( 1 log 1)
 * So it's O ( sum(i = 1 to n) of i log i). I'm not if that can be simplified, but I do know that sum(i = 1 to n) of i is n(n + 1)/2.  So your algorithm will be worse than O (n ^ 2).
 * I don't think that on average, things will be much faster. Let me think about it and see if I can come up with an answer for that.--Ryan Stone 21:03, 18 Feb 2005 (UTC)

 * Well, I've thought about this a bit more, and what I realized was that even if Gkhan's algorithm was faster in the average case, it still probably couldn't beat quicksort. Heapsort's greatest advantages over quicksort is its guaranteed O (n log n) and that it's an in-place sort.  If you're willing accept poor performance on certain inputs anyway, you might as well go with quicksort.--Ryan Stone 02:08, 23 Feb 2005 (UTC)

pseudocode question #2
When getting the child, is multiplying root * 2 enough? I mean, root = 0, then child = 0? I'm thinking it should be ((root + 1) * 2) - 1
 * For the sake of simplicity, the arrays are one-based. However, this should have been explicitly noted and now is. Thanks. Deco 02:01, 26 Jun 2005 (UTC)
 * Oops, I was wrong here. It seems like other parts rely on it being zero-based. Hmm. Deco 28 June 2005 21:17 (UTC)

The comment that Heapsort is usually faster than Mergesort may be a bit dated.

On architectures with a (relatively) small CPU cache and large main memory (e.g. Pentiums), Heapsort is usually *much* slower than Mergesort, when the size of the array being sorted is significantly larger than that of the cache but less than half that of main memory, *because* there are so many cache misses (the penalty is appalling: on my home PC a Heapsort of, say, 500,000 32-bit integers takes about twice as long, and of 90,000,000, takes about 10 times as long, as Mergesort and Quicksort).

Heapsort should *not* be used for large N.

Re: the "sorting revisited" link: it just ain't so. By a stroke of luck, the v8 Intel C++ compiler optimizes binary Heapsort better than it optimizes Quicksort or Mergesort (if mergesort is coded in assembler to avoid branch mis-predictions it is slightly faster) (but I'll be damned if I can dream up an efficient way to do the same thing for Quicksort!). The analysis doesn't extend to *large* values of N, which is where Heapsort does very badly indeed. The Insertion Sort implementation used for the test cases is... non-standard and very inefficient... which knobbles both Quicksort and Mergesort. I recommend: *Pull* the link.

-James Barbetti
 * This is interesting. I wasn't aware that heapsort had such terrible cache behaviour, but it makes sense considering its access pattern. I can add something regarding this. Deco 19:55, 11 July 2005 (UTC)

Pseudocode question #3
How does the following line of code translate to other languages?

var int root = start, child

How can two variables be assigned to a single varaiable? Can someone please explain how this works and perhaps split this line up into something that can carry over more easily into other languages?

Thank you -- Random Heapsort Investigator

 * Presumably, it's like C, where int x, y; declares both x and y as integers. One can make an assignment as well, so int x = 2, y; declares both x and y as integers and sets x to be 2. Dysprosia 03:36, 15 August 2006 (UTC)

Pseudocode question #4
Is it true that both heapifys run in O(n)? The one that uses siftUp should perform

sum_{i=2}^{i=n} floor(log_2(i))

comparisons in the wost case (every new element is shifted all the way to the root). If a recall correctly, the previous summation is \theta(n log n). 193.120.148.177 20:50, 12 September 2007 (UTC)

 * Oops, I didn't notice that this issue had already been raised when I posted my comment under "Heapify approaches are equivalent?" below. Since we both questioned the statement independently, I'm going to take that as consensus and fix it. Peristarkawan 22:02, 28 September 2007 (UTC)

Quicksort not in-place
Isn't it inappropriate to state that an advantage of Heapsort over QuickSort is that Heapsort is in-place? After all, QuickSort seems to be easily done in-place as shown in the Quicksort article.

Quote:

 * Quicksort is not in place, as the article discusses at some length. Quicksort often uses an in-place partition, and has a space-saving tail-recursive variant, but even then it requires Ω(log n) space. The quote you gave is actually talking about heapsort, so it's an argument against your claim rather than for. Deco 00:30, 6 December 2005 (UTC)

is smoothsort the same as heapsort?
It seems smoothsort redirects to heapsort. Does this make sense? The table on sorting algorithm lists both heapsort and smoothsort as seperate. --Apantomimehorse 21:21, 20 August 2006 (UTC)

I noticed the same thing. Have a look under "Variations" and they do talk about smoothsort though.

http://en.wikipedia.org/wiki/Smoothsort#Variations

Blakeops 06:40, 2 February 2007 (UTC)

 * SelectionSort, HeapSort, and SmoothSort are all variations on the idea of "find the largest element in the unsorted part of the list and add it to the sorted part". Their main difference is in how they structure the unsorted part of the list: SelectionSort doesn't bother to structure it; HeapSort structures it as a heap; SmoothSort structures it in a way that doesn't have a name.

 * As a result, HeapSort's performance is O(nlog(n)) in all cases whereas SelectionSort's performance is always O(n2) and SmoothSort's performance is O(n) in the best case and O(nlog(n)) in the worst case.

 * While it's fair to say that SmoothSort was inspired by HeapSort, I think that it's as misleading to say that SmoothSort is a variation of HeapSort as it would be to say that SmoothSort is a variation of SelectionSort. There's no doubt that at a high enough level they have something in common but then so do all sorting algorithms. -- Derek Ross | Talk 18:14, 8 May 2008 (UTC)

correcting a heapsort reference
chuck bradley, bradley@tiac.net the reference to introduction to algorithms is partly wrong. chpt 6 is called heapsort. it covers heaps, heapsort, and priority queues. chapter 7 is quicksort.

Two versions of the code?
The second version of the pseudocode gives a feeling of dissonance to this article. I think it's because of the way the intro to the second version complains slightly about the example before it. Can something be done to correct this? --Masamage 17:14, 7 December 2006 (UTC)

Pseudocode changes and clarifications
The strange thing about the above implementation is that it uses heapify-down operations to achieve what we really want to achieve using heapify-up operations. Imagine building the heap. As we add new elements, we want them to crawl up the heap. For the actual sorting, however, the standard implementation jibes with intuition. The following implementation jibes completely with intuition and is still O(n log n). The two implementations are equivalent, except in the order in which they process data. The first one starts at the bottom and moves up while sifting down, while the second starts at the top and moves down while sifting up. Either way is acceptable and neither is strange to me. The only plus side to using the first piece of code is that you only need one sift function, other than that they are equivalent in execution time.

I am having trouble understanding some of the notation used in this function. function siftup(a, start) { var int child := start, root, remainder while child > 0 { remainder := (child - 1) % 2 root := ((child - 1) - remainder) / 2 if a[root] < a[child] swap(a[root], a[child]) child := root else return } } So I rewrote it. Most languages default to integer division operations when using integers. So unless start, child, and/or root are defined as floating point they are unlikly to cause floating point division in the Java, or C languages. This algorithm is correct, but the remainder is (in this algorithm) equivalent to using the floor function.

I changed the original sift down function to take the end as a parameter instead of count, because it may be difficult to understand that sift(a, 0, end) means to sift down all the way except for the last element in the heap as you are inputting end for count. I also changed the format to be in greater accordence with Algorithms_on_Wikipedia. --ANONYMOUS COWARD0xC0DE 08:10, 18 December 2006 (UTC)

Heapsort Explanation
The article is pretty good at showing the logic behind heapsort. I'm going to attempt to explain this, then present an example. After the numbers or fields are loaded into an array, think of the heap as a corporation where each supervisor has one or two people reporting to them. The first number A(1) is the CEO. The next two numbers, A(2) and A(3) report to A(1). The next two numbers, A(4) and A(5) report to A(2), A(6) and A(7) report to A(3), A(8) and A(9) report to A(4). If there are an even number of entries, then the last supervisor only has one person reporting to them. Thus, for any supervisor J, there will be up to two employees, A(2J) and A(2J+1) reporting to them. Therefore, in a company of N employees, int(N/2) of those employees are supervisors.

We start off with the last supervisor, int(N/2)=J, and compare A(J) with his one or two subordinates, A(2J) and A(2J+1). If N is even, then the last supervisor only has one employee reporting to him, A(2J). Between the three people, the supervisor must have the highest numbers. Then we move backwards through the supervisors and compare each supervisor with his two employees. When we get to A(1), then A(1) will have the highest value. Then we switch the value of the CEO, A(1), with the last employee, A(N) so A(N) will have the highest number. Then A(N) will retire, so there are N - 1 employees left. We then recalculate the number of supervisors, which is int((N-1)/2), work backwards from the last supervisor in N-1 employees. Then when A(1) has the highest value, we switch A(1) with the last employee, which is now A(N-1) and A(N-1) retires. Now there are N-2 employees and int((N-2)/2) supervisors and continue these comparison until there is only one employee left. Here is the logic for that.

LET N = NUMBER OF RECORDS LET J = N WHILE J > 1 I = INT(J/2) 'Calculate number of supervisors While I > 0 If A(I) < A(2I) then TEMP=A(I)  'Supervisor gets highest value. A(I)=A(2I) A(2I)=TEMP End If   If A(I) < A(2I+1) and 2I+1 <= J then TEMP=A(I)  'Supervisor gets highest value. A(I)=A(2I+1) A(2I+1)=TEMP End If   I = I - 1  'Go backward through the supervisors Loop TEMP=A(J)   'Switch CEO and last employee. A(J)=A(1) A(1)=TEMP J = J - 1   'Retire last employee LOOP K=1 WHILE K <= N PRINT A(K) K = K + 1 LOOP --Trust101 07:22, 27 April 2007 (UTC)

Wikibook Quotation
Why not to use implementation suggested in Wikibook Algorithm implementation? KorDen 16:27, 20 February 2007 (UTC)

heapsort variant and heapsort generalization
There is a relatively simple variation (exchanging two values instead of one during each Heapsort iteration) that saves N/2 comparisons and N/2 moves. The variation is described in the paper at http://www.eduneer.com/pub/dualheapsort.pdf, which also may be of interest to those reading the heapsort article.

Gj7 16:21, 20 June 2007 (UTC)

Heapify approaches are equivalent?
"It can be shown that both variants of heapify run in O(n) time."

I'm fairly certain that this is incorrect. One half of the nodes in a heap are leaves. When using the siftUp variant, sifting up from each leaf node will take Θ(log n) time in the worst case, making the algorithm Ω(n log n). The asymptotic complexity of the siftDown variant is harder to demonstrate, but my recollection from school is that it is in fact O(n). – Peristarkawan 02:42, 28 September 2007 (UTC)

Code block templates
Hi all. A while ago I began an experiment with a new method for discouraging incorrect good-faith changes to code and pseudocode called "code block templates" on the articles quicksort and binary search algorithm. So far there haven't been any incorrect new changes to those code block templates, but very few changes have been made, so I'd like to expand the scope of this experiment to see how effective it is. This is one of the articles I'm targeting for this second phase. Please let me know on my talk page if you have any questions or concerns. Thanks! Dcoetzee 21:37, 7 December 2008 (UTC)

Bug in pseudocode?
If I read it right, then it doesn't sort the simple vector: {1,2}. If I'm right then it's because after the swap (when poping elements), the sift operations still includes the poped element. While it shouldn't.

79.178.112.120 (talk) 21:48, 10 July 2009 (UTC)

Sorting an almost sorted list
When you heap sort a list that is "almost sorted" or even completely sorted (like if you just added 1 element), heapsort makes a complete full sort, by recreating the entire heap, and moving just about every element in the list.

Isn't that a big disadvantage to a sort method like even the basic bubble sort, which can do a 1 pass sort?

Shouldn't that be mentioned in the article? happypal (Talk | contribs) 08:39, 30 July 2009 (UTC)

Proof that heapify with siftDown is O(n) and not just O(n log n)
Each level k has 2k-1 elements (counting levels from 1 to log n). In the worst case scenario of fully sorted array, each element has to be pushed to the end. So siftDown at level k will take (log n) - k  operations, since the new parent is the smallest element, so it will siftDown to the bottom. So at each level k you have 2k-1 elements to be siftDown, each taking (log n) - k, or Sum[1, log n] (2k-1(log n - k)) = S(2k-1 log n - 2k-1 k) = log n S(2k-1) - S(k 2k-1) = log n (2log n - 1) - ( 2 + 2log n(log n - 1) ) = log n (n - 1) - ( 2 + n(log n - 1) ) =    // replaced 2log n with n n log n - log n - 2 - n log n + n = n - log n - 2 = O(n) For comparison, heapify with siftUp takes O(n log n) This time, each level k takes k-1 operations to siftUp in worst case. Let's look at the last level log n. It contains 2log n - 1 or n/2 elements. Pushing them up takes n/2 elements pushing up log n - 1 levels. Or total for last level: (log n - 1)*n/2 = O(n log n)

Pla123 (talk) 00:49, 16 January 2010 (UTC)

Pictures to Step through algorithm?
Hi all. I was wondering if we could get any pictures that step through the algorithm? The one's on Prim's algorithm, and Kruskal's algorithm are particularly useful. I am more of a visual learner, and the pictures are 10x easier to understand than the pseudocode. thoughts? Crabpot8 (talk) 17:45, 10 February 2009 (UTC)

 * Maybe someone could use this: http://corte.si/posts/code/visualisingsorting/index.html 84.182.107.93 (talk) 16:49, 9 February 2010 (UTC)

Best Case Run Time
Can someone tell me an instance where the best case would be O(n)? I think this is an error. Epachamo (talk) 21:45, 15 October 2011 (UTC)

The best case is achieved when all elements are identical. — Preceding unsigned comment added by 89.0.35.62 (talk) 20:55, 25 January 2014 (UTC)

Is Heapsort a stable sort algorithm or not ?
I think that heapsort - like each other sort algorithm - can be both a stable sort algorithm or not. This depends in my opinion only on the concrete implementation of the sort algorithm.

If we assume that the given array of elements is already sorted by any sort keys (SortKey_0, SortKey_1, ..., SortKey_I-1) so (considering all the already processed sort keys) all elements with a lower array index are lower or equal to all the elements with a larger array index. This already existing sort order (of all the already processed sort keys) should be changed (for the current SortKey_I) in both of the following to cases: if the value of an element with a lower array index (parent) is greater then OR is equal to the value of an element with a larger array index (one of it's children). This really little change in the pseudo code (two times replace operator ">" with operator ">=") should guarantee that from all elements with the same value (considering the current SortKey_I) that element with the largest array index as first is swapped to the root element and finally stored at the end of the array. That means the already existing sort order (of all the already processed sort keys) will be unchanged now if the values of two different elements are equal (considering the current SortKeyI). For this reason this sort algorithm should be stable now. Is this correct?

Aragorn321 (talk) 11:12, 18 July 2012 (UTC)

 * No, this doesn't work, although it's a common student question. The problem is that elements move, and after they move their order is no longer the same as their initial order.  (You can easily do it by storing the initial position, and using that as part of the sort key, but a stable sort shouldn't need that.)
 * Basically, two elements with the same value might have different parents. And then the element with the greater parent is promoted a level when some other element is sifted down.  This can move it from after its twin to before in the array (higher in the heap).
 * 71.41.210.146 (talk) 20:18, 26 December 2016 (UTC)

Merge Sort requires requires Ω(n) auxiliary space - really?
"Heapsort also competes with merge sort, which has the same time bounds, but requires Ω(n) auxiliary space, whereas heapsort requires only a constant amount."

This is NOT true, since merging can be done in-place in O(n) time. — Preceding unsigned comment added by Dhruvbird (talk • contribs) 02:19, 13 August 2012 (UTC)

 * Do you have a reference that says a stable in-place merge takes O(n) time? References are really what WP requires. A stable out-of-place merge can be done in O(n) time. Stable merging in-place is a bit trickier -- what happens to displaced elements? Glrx (talk) 16:17, 14 August 2012 (UTC)

 * The constant factor tends to be a problem in practice, but O(n) algorithms are well known. 71.41.210.146 (talk) 20:04, 26 December 2016 (UTC)

"Now repeat after" me problem
I highly object to the code that is introduced in this wiki. Either write a pseudo-code that illustrates the idea or write a concise code where the idea is obvious. Writing a code that is optimized in any way, which always means more difficult to read is really not good. I have seen in many books the same, sorry to say, but mess

if a[swap] < a[child] swap ← child if child+1 ≤ end and a[swap] < a[child+1] swap ← child + 1 if swap ≠ root swap(a[root], a[swap]) root ← swap           (: repeat to continue sifting down the child now :) else return

where special case child+1 ≤ end is mixed with everything else. There is no reason for sift-up and sift-down to look this much different in code, while they are the same basic idea. I know that one can object and say that in most literature this is how this algorithm is presented, I am just saying that it is better then to leave just the idea in pseudo-code with a reference to the literature, than to repeat one option. The problem is that, if you present the subject this way, as it is here and in other places other algorithms, you make an already subtle subject even more complicated for no reason. (I truly do not understand why everything I can read is cleared and brought to higher and higher levels of abstraction, precision and simplification everywhere, except in programming. The solution that was taught 30 years ago is the same as today down to the last line. Mind-boggling for me.) — Preceding unsigned comment added by Aperisic (talk • contribs) 16:35, 18 February 2014 (UTC)

Algorithm issues - pseudocode does not work
duplicate keys?

none in any code I find, but there certainly are in "the real world"

if both children are >= "swap"

[terrible name - same as procedure in pseudocode - could be "swapHere"]

if a[swap] < a[child] swap ← child  if child+1 ≤ end and a[swap] < a[child+1] swap ← child + 1

How is the fact that the first assignment may be overwritten acceptable?

problem confirmed - implemented first block of pseudocode - fails to sort array — Preceding unsigned comment added by 68.183.37.136 (talk • contribs) 03:26, 4 June 2014

 * Look at the code again. The assignment is not "overwritten" / thrown away in the sense you imply. The heap must promote the largest element to the parental position. The index value  starts out as the parent index. If the left child is greater, then   is set to the child. If there is a right child and the right child is greater than what   currently points to (the larger of parent and left child), then   is set to the right child. The result is   is the index of the largest of the parent its two children. Then that index and the index of the parent are swapped to promote the largest of the three values to the parental position. Glrx (talk) 01:06, 13 June 2014 (UTC)

Non-Optimal Algorithm Used
172.56.32.126 (talk) 04:53, 26 January 2015 (UTC) 2015-01-25: I think this page has an interesting issue. Instead of heapify putting the max element on the left of the array, I don't see why we cannot just put the max element on the right instead. Doing so will save us around N swaps right away.

 * In an $O(n log(n))$ sorting algorithm, saving $n$ swaps does not have an impact. Reliable sources put the root (the heap max) on the left, so we don't get to say different: rewriting the algorithm would be original research. Furthermore, putting the root on the right to avoid the copy means the entire heap would need to shift to the left (or a different heap structure would be needed). Glrx (talk) 16:50, 31 January 2015 (UTC)

Pseudocode question #5
In this snippet of pseudocode procedure heapify(a, count) is   (start is assigned the index in 'a' of the last parent node) (the last element in a 0-based array is at index count-1; find the parent of that element) start ← floor ((count - 2) / 2) Is the (count-2) correct? The previous line says it should be (count-1), shouldn't it? — Preceding unsigned comment added by A.s.serov (talk • contribs) 11:44, 23 June 2015 (UTC)
 * . Glrx (talk) 01:26, 27 June 2015 (UTC)

Request to change the algorithm
The following code of heapify with siftDown is very complex, and isn't explained why it works and why it's correct. (For example, I even believe it's wrong.) A much simpler version of heapify using siftUp must be used as the basic code. Then siftDown version can be presented as a little better alternative.

(Put elements of 'a' in heap order, in-place) procedure heapify(a, count) is   (start is assigned the index in 'a' of the last parent node) (the last element in a 0-based array is at index count-1; find the parent of that element) start ← iParent(count-1) while start ≥ 0 do       (sift down the node at index 'start' to the proper place such that all nodes below         the start index are in heap order) siftDown(a, start, count - 1) (go to the next parent node) start ← start - 1 (after sifting down the root all nodes/elements are in heap order)

Zyavrik (talk) 02:17, 12 May 2019 (UTC)

Contentious issue about siftDown function
I had made some changes in the siftDown function which seemed to correct a mistake in my view. (This was my first ever edit), The change I made was reverted twice, so I think it should be discussed here.

My original change was done November 17th. at 3:51, I included the following message:

'''There is a mistake in the siftDown pseudo-code, the last assingment has to be "swap = root", not "root = swap" - this causes the method to halt. Check https://github.com/pat-jpnk/algorithms/blob/main/sorting/heapsort.py for working example '''

Am I wrong ?

Pat-jpnk (talk) 12:12, 11 December 2021 (UTC)
 * I was notified of this by another editor. The pseudocode on this article is correct. The error is in your implementation, of which there's a few issues. Firstly, you're missing the heapify function. In its place you have a recursive perculate function, that looks like it's doing a simple bubble sort as max_heap iterates over the array it is invoked with. Next you're feeding the result of the bubble sort into heap sort, however you have two mistakes in your sift_down function. On line 55, where you're doing the calculation  you should instead be doing  . The reason for this is that at each of those lines you want to get the left child of whatever the current value of root is, whereas your code gets the left child of whatever the current value of start is. This is more obvious when you put that calculation off into a function as in the pseudocode example. Once you fix those two lines, line 70 should read   and your code should execute properly. Sideswipe9th (talk) 22:47, 13 December 2021 (UTC)

Thanks for your input!

O(N^2) heapsort code using siftUp
I think the version of heapsort using siftUp needs to be fixed or removed. As currently written heapsort using siftUp is an O(N^2) algorithm at best because of the repeated calls to heapify which itself is O(N log(N)). Currently it's presented as an alternative O(N log(N)) heapsort implementation and that appears to be a mistake. The writing also gives the impression that this is Williams' original algorithm but I believe that although his original algorithm used siftUp in heapify it still made use of siftDown in the heapsort procedure itself. So this version is neither historically relevant nor performant enough to warrant inclusion in the article. I've copied and pasted the current code below for reference.

procedure heapify(a,count) is     (end is assigned the index of the first (left) child of the root) end := 1 while end < count (sift up the node at index end to the proper place such that all nodes above          the end index are in heap order) siftUp(a, 0, end) end := end + 1 (after sifting up the last node all nodes are in heap order)

procedure heapsort(a, count) is input: an unordered array a of length count (Build the heap in array a so that largest value is at the root) heapify(a, count) (The following loop maintains the invariants that a[0:end] is a heap and every element     beyond end is greater than everything before it (so a[end:count] is in sorted order)) end ← count - 1 while end > 0 do (a[0] is the root and largest value. The swap moves it in front of the sorted elements.) swap(a[end], a[0]) (rebuild the heap using siftUp after the swap ruins the heap property) heapify(a, end) (reduce the heap size by one) end ← end - 1 — Preceding unsigned comment added by Mithrandir314 (talk • contribs) 01:50, 10 March 2022 (UTC)

siftDown in Pseudocode is incorrect?
swap ← root will overwrite swap ← child or swap ← child + 1, possibly looping infinitely. swap ← root should move out of the while loop?

Comments in pseudocode?
I find that using brackets for comments is quite unreadable, especially since brackets are already being used for function calls. Permission to change the format?

Probably something like this: (this is a comment)

to this: // this is a comment COArSe D1RTxxx (talk) 22:30, 27 September 2023 (UTC)

 * Adding whitespace and color would be more helpful, I think. Compare:

while end > 0 do (a[0] is the root and largest value.) swap(a[end], a[0]) (the heap size is reduced by one) end ← end - 1 (the swap ruined the heap property, so restore it) siftDown(a, 0, end)

with

while end > 0 do (a[0] is the root and largest value.) swap(a[end], a[0]) (the heap size is reduced by one) end ← end - 1 (the swap ruined the heap property, so restore it) siftDown(a, 0, end)

 * Dexxor (talk) 12:52, 28 September 2023 (UTC)

title: Talk:Heapsort


text:
Histone

In biology, histones are highly basic proteins abundant in lysine and arginine residues that are found in eukaryotic cell nuclei and in most Archaeal phyla. They act as spools around which DNA winds to create structural units called nucleosomes. Nucleosomes in turn are wrapped into 30-nanometer fibers that form tightly packed chromatin. Histones prevent DNA from becoming tangled and protect it from DNA damage. In addition, histones play important roles in gene regulation and DNA replication. Without histones, unwound DNA in chromosomes would be very long. For example, each human cell has about 1.8 meters of DNA if completely stretched out; however, when wound about histones, this length is reduced to about 90 micrometers (0.09 mm) of 30 nm diameter chromatin fibers.

There are five families of histones which are designated H1/H5 (linker histones), H2, H3, and H4 (core histones). The nucleosome core is formed of two H2A-H2B dimers and a H3-H4 tetramer. The tight wrapping of DNA around histones is to a large degree a result of electrostatic attraction between the positively charged histones and negatively charged phosphate backbone of DNA.

Histones may be chemically modified through the action of enzymes to regulate gene transcription. The most common modification are the methylation of arginine or lysine residues or the acetylation of lysine. Methylation can affect how other protein such as transcription factors interact with the nucleosomes. Lysine acetylation eliminates a positive charge on lysine thereby weakening the electrostatic attraction between histone and DNA resulting in partial unwinding of the DNA making it more accessible for gene expression.

Classes and variants
Five major families of histone proteins exist: H1/H5, H2A, H2B, H3, and H4. Histones H2A, H2B, H3 and H4 are known as the core or nucleosomal histones, while histones H1/H5 are known as the linker histones.

The core histones all exist as dimers, which are similar in that they all possess the histone fold domain: three alpha helices linked by two loops. It is this helical structure that allows for interaction between distinct dimers, particularly in a head-tail fashion (also called the handshake motif). The resulting four distinct dimers then come together to form one octameric nucleosome core, approximately 63 Angstroms in diameter (a solenoid (DNA)-like particle). Around 146 base pairs (bp) of DNA wrap around this core particle 1.65 times in a left-handed super-helical turn to give a particle of around 100 Angstroms across. The linker histone H1 binds the nucleosome at the entry and exit sites of the DNA, thus locking the DNA into place and allowing the formation of higher order structure. The most basic such formation is the 10 nm fiber or beads on a string conformation. This involves the wrapping of DNA around nucleosomes with approximately 50 base pairs of DNA separating each pair of nucleosomes (also referred to as linker DNA). Higher-order structures include the 30 nm fiber (forming an irregular zigzag) and 100 nm fiber, these being the structures found in normal cells. During mitosis and meiosis, the condensed chromosomes are assembled through interactions between nucleosomes and other regulatory proteins.

Histones are subdivided into canonical replication-dependent histones, whose genes are expressed during the S-phase of the cell cycle and replication-independent histone variants, expressed during the whole cell cycle. In mammals, genes encoding canonical histones are typically clustered along chromosomes in 4 different highly-conserved loci, lack introns and use a stem loop structure at the 3' end instead of a polyA tail. Genes encoding histone variants are usually not clustered, have introns and their mRNAs are regulated with polyA tails. Complex multicellular organisms typically have a higher number of histone variants providing a variety of different functions. Recent data are accumulating about the roles of diverse histone variants highlighting the functional links between variants and the delicate regulation of organism development. Histone variants proteins from different organisms, their classification and variant specific features can be found in "HistoneDB 2.0 - Variants" database. Several pseudogenes have also been discovered and identified in very close sequences of their respective functional ortholog genes.

The following is a list of human histone proteins, genes and pseudogenes:

Structure

The nucleosome core is formed of two H2A-H2B dimers and a H3-H4 tetramer, forming two nearly symmetrical halves by tertiary structure (C2 symmetry; one macromolecule is the mirror image of the other). The H2A-H2B dimers and H3-H4 tetramer also show pseudodyad symmetry. The 4 'core' histones (H2A, H2B, H3 and H4) are relatively similar in structure and are highly conserved through evolution, all featuring a 'helix turn helix turn helix' motif (DNA-binding protein motif that recognize specific DNA sequence). They also share the feature of long 'tails' on one end of the amino acid structure - this being the location of post-translational modification (see below).

Archaeal histone only contains a H3-H4 like dimeric structure made out of a single type of unit. Such dimeric structures can stack into a tall superhelix ("hypernucleosome") onto which DNA coils in a manner similar to nucleosome spools. Only some archaeal histones have tails.

The distance between the spools around which eukaryotic cells wind their DNA has been determined to range from 59 to 70 Å.

In all, histones make five types of interactions with DNA:
 * Salt bridges and hydrogen bonds between side chains of basic amino acids (especially lysine and arginine) and phosphate oxygens on DNA
 * Helix-dipoles form alpha-helixes in H2B, H3, and H4 cause a net positive charge to accumulate at the point of interaction with negatively charged phosphate groups on DNA
 * Hydrogen bonds between the DNA backbone and the amide group on the main chain of histone proteins
 * Nonpolar interactions between the histone and deoxyribose sugars on DNA
 * Non-specific minor groove insertions of the H3 and H2B N-terminal tails into two minor grooves each on the DNA molecule

The highly basic nature of histones, aside from facilitating DNA-histone interactions, contributes to their water solubility.

Histones are subject to post translational modification by enzymes primarily on their N-terminal tails, but also in their globular domains. Such modifications include methylation, citrullination, acetylation, phosphorylation, SUMOylation, ubiquitination, and ADP-ribosylation. This affects their function of gene regulation.

In general, genes that are active have less bound histone, while inactive genes are highly associated with histones during interphase. It also appears that the structure of histones has been evolutionarily conserved, as any deleterious mutations would be severely maladaptive. All histones have a highly positively charged N-terminus with many lysine and arginine residues.

Evolution and species distribution
Core histones are found in the nuclei of eukaryotic cells and in most Archaeal phyla, but not in bacteria. The unicellular algae known as dinoflagellates were previously thought to be the only eukaryotes that completely lack histones, but later studies showed that their DNA still encodes histone genes. Unlike the core histones, homologs of the lysine-rich linker histone (H1) proteins are found in bacteria, otherwise known as nucleoprotein HC1/HC2.

It has been proposed that core histone proteins are evolutionarily related to the helical part of the extended AAA+ ATPase domain, the C-domain, and to the N-terminal substrate recognition domain of Clp/Hsp100 proteins. Despite the differences in their topology, these three folds share a homologous helix-strand-helix (HSH) motif. It's also proposed that they may have evolved from ribosomal proteins (RPS6/RPS15), both being short and basic proteins.

Archaeal histones may well resemble the evolutionary precursors to eukaryotic histones. Histone proteins are among the most highly conserved proteins in eukaryotes, emphasizing their important role in the biology of the nucleus. In contrast mature sperm cells largely use protamines to package their genomic DNA, most likely because this allows them to achieve an even higher packaging ratio.

There are some variant forms in some of the major classes. They share amino acid sequence homology and core structural similarity to a specific class of major histones but also have their own feature that is distinct from the major histones. These minor histones usually carry out specific functions of the chromatin metabolism. For example, histone H3-like CENPA is associated with only the centromere region of the chromosome. Histone H2A variant H2A.Z is associated with the promoters of actively transcribed genes and also involved in the prevention of the spread of silent heterochromatin. Furthermore, H2A.Z has roles in chromatin for genome stability. Another H2A variant H2A.X is phosphorylated at S139 in regions around double-strand breaks and marks the region undergoing DNA repair. Histone H3.3 is associated with the body of actively transcribed genes.

Compacting DNA strands
Histones act as spools around which DNA winds. This enables the compaction necessary to fit the large genomes of eukaryotes inside cell nuclei: the compacted molecule is 40,000 times shorter than an unpacked molecule.

Chromatin regulation

Histones undergo posttranslational modifications that alter their interaction with DNA and nuclear proteins. The H3 and H4 histones have long tails protruding from the nucleosome, which can be covalently modified at several places. Modifications of the tail include methylation, acetylation, phosphorylation, ubiquitination, SUMOylation, citrullination, and ADP-ribosylation. The core of the histones H2A and H2B can also be modified. Combinations of modifications, known as histone marks, are thought to constitute a code, the so-called "histone code". Histone modifications act in diverse biological processes such as gene regulation, DNA repair, chromosome condensation (mitosis) and spermatogenesis (meiosis).

The common nomenclature of histone modifications is:
 * The name of the histone (e.g., H3)
 * The single-letter amino acid abbreviation (e.g., K for Lysine) and the amino acid position in the protein
 * The type of modification (Me: methyl, P: phosphate, Ac: acetyl, Ub: ubiquitin)
 * The number of modifications (only Me is known to occur in more than one copy per residue. 1, 2 or 3 is mono-, di- or tri-methylation)

So H3K4me1 denotes the monomethylation of the 4th residue (a lysine) from the start (i.e., the N-terminal) of the H3 protein.

Modification

A huge catalogue of histone modifications have been described, but a functional understanding of most is still lacking. Collectively, it is thought that histone modifications may underlie a histone code, whereby combinations of histone modifications have specific meanings. However, most functional data concerns individual prominent histone modifications that are biochemically amenable to detailed study.

Lysine methylation

The addition of one, two, or many methyl groups to lysine has little effect on the chemistry of the histone; methylation leaves the charge of the lysine intact and adds a minimal number of atoms so steric interactions are mostly unaffected. However, proteins containing Tudor, chromo or PHD domains, amongst others, can recognise lysine methylation with exquisite sensitivity and differentiate mono, di and tri-methyl lysine, to the extent that, for some lysines (e.g.: H4K20) mono, di and tri-methylation appear to have different meanings. Because of this, lysine methylation tends to be a very informative mark and dominates the known histone modification functions.

Glutamine serotonylation
Recently it has been shown, that the addition of a serotonin group to the position 5 glutamine of H3, happens in serotonergic cells such as neurons. This is part of the differentiation of the serotonergic cells. This post-translational modification happens in conjunction with the H3K4me3 modification. The serotonylation potentiates the binding of the general transcription factor TFIID to the TATA box.

Arginine methylation

What was said above of the chemistry of lysine methylation also applies to arginine methylation, and some protein domains—e.g., Tudor domains—can be specific for methyl arginine instead of methyl lysine. Arginine is known to be mono- or di-methylated, and methylation can be symmetric or asymmetric, potentially with different meanings.

Arginine citrullination
Enzymes called peptidylarginine deiminases (PADs) hydrolyze the imine group of arginines and attach a keto group, so that there is one less positive charge on the amino acid residue. This process has been involved in the activation of gene expression by making the modified histones less tightly bound to DNA and thus making the chromatin more accessible. PADs can also produce the opposite effect by removing or inhibiting mono-methylation of arginine residues on histones and thus antagonizing the positive effect arginine methylation has on transcriptional activity.

Lysine acetylation

Addition of an acetyl group has a major chemical effect on lysine as it neutralises the positive charge. This reduces electrostatic attraction between the histone and the negatively charged DNA backbone, loosening the chromatin structure; highly acetylated histones form more accessible chromatin and tend to be associated with active transcription. Lysine acetylation appears to be less precise in meaning than methylation, in that histone acetyltransferases tend to act on more than one lysine; presumably this reflects the need to alter multiple lysines to have a significant effect on chromatin structure. The modification includes H3K27ac.

Serine/threonine/tyrosine phosphorylation

Addition of a negatively charged phosphate group can lead to major changes in protein structure, leading to the well-characterised role of phosphorylation in controlling protein function. It is not clear what structural implications histone phosphorylation has, but histone phosphorylation has clear functions as a post-translational modification, and binding domains such as BRCT have been characterised.

Effects on transcription
Most well-studied histone modifications are involved in control of transcription.

Actively transcribed genes
Two histone modifications are particularly associated with active transcription:
 * Trimethylation of H3 lysine 4 (H3K4me3): This trimethylation occurs at the promoter of active genes  and is performed by the COMPASS complex.   Despite the conservation of this complex and histone modification from yeast to mammals, it is not entirely clear what role this modification plays. However, it is an excellent mark of active promoters and the level of this histone modification at a gene's promoter is broadly correlated with transcriptional activity of the gene. The formation of this mark is tied to transcription in a rather convoluted manner: early in transcription of a gene, RNA polymerase II undergoes a switch from initiating' to 'elongating', marked by a change in the phosphorylation states of the RNA polymerase II C terminal domain (CTD). The same enzyme that phosphorylates the CTD also phosphorylates the Rad6 complex,  which in turn adds a ubiquitin mark to H2B K123 (K120 in mammals). H2BK123Ub occurs throughout transcribed regions, but this mark is required for COMPASS to trimethylate H3K4 at promoters.
 * Trimethylation of H3 lysine 36 (H3K36me3): This trimethylation occurs in the body of active genes and is deposited by the methyltransferase Set2. This protein associates with elongating RNA polymerase II, and H3K36Me3 is indicative of actively transcribed genes. H3K36Me3 is recognised by the Rpd3 histone deacetylase complex, which removes acetyl modifications from surrounding histones, increasing chromatin compaction and repressing spurious transcription.  Increased chromatin compaction prevents transcription factors from accessing DNA, and reduces the likelihood of new transcription events being initiated within the body of the gene. This process therefore helps ensure that transcription is not interrupted.

Repressed genes
Three histone modifications are particularly associated with repressed genes:
 * Trimethylation of H3 lysine 27 (H3K27me3): This histone modification is deposited by the polycomb complex PRC2. It is a clear marker of gene repression, and is likely bound by other proteins to exert a repressive function. Another polycomb complex, PRC1, can bind H3K27me3 and adds the histone modification H2AK119Ub which aids chromatin compaction. Based on this data it appears that PRC1 is recruited through the action of PRC2, however, recent studies show that PRC1 is recruited to the same sites in the absence of PRC2.
 * Di and tri-methylation of H3 lysine 9 (H3K9me2/3): H3K9me2/3 is a well-characterised marker for heterochromatin, and is therefore strongly associated with gene repression. The formation of heterochromatin has been best studied in the yeast Schizosaccharomyces pombe, where it is initiated by recruitment of the RNA-induced transcriptional silencing (RITS) complex to double stranded RNAs produced from centromeric repeats. RITS recruits the Clr4 histone methyltransferase which deposits H3K9me2/3. This process is called histone methylation. H3K9Me2/3 serves as a binding site for the recruitment of Swi6 (heterochromatin protein 1 or HP1, another classic heterochromatin marker) which in turn recruits further repressive activities including histone modifiers such as histone deacetylases and histone methyltransferases.
 * Trimethylation of H4 lysine 20 (H4K20me3): This modification is tightly associated with heterochromatin, although its functional importance remains unclear. This mark is placed by the Suv4-20h methyltransferase, which is at least in part recruited by heterochromatin protein 1.

Bivalent promoters
Analysis of histone modifications in embryonic stem cells (and other stem cells) revealed many gene promoters carrying both H3K4Me3 and H3K27Me3, in other words these promoters display both activating and repressing marks simultaneously. This peculiar combination of modifications marks genes that are poised for transcription; they are not required in stem cells, but are rapidly required after differentiation into some lineages. Once the cell starts to differentiate, these bivalent promoters are resolved to either active or repressive states depending on the chosen lineage.

DNA damage repair
Marking sites of DNA damage is an important function for histone modifications. Without a repair marker, DNA would get destroyed by damage accumulated from sources such as the ultraviolet radiation of the sun.
 * Phosphorylation of H2AX at serine 139 (γH2AX): Phosphorylated H2AX (also known as gamma H2AX) is a marker for DNA double strand breaks, and forms part of the response to DNA damage. H2AX is phosphorylated early after detection of DNA double strand break, and forms a domain extending many kilobases either side of the damage. Gamma H2AX acts as a binding site for the protein MDC1, which in turn recruits key DNA repair proteins (this complex topic is well reviewed in ) and as such, gamma H2AX forms a vital part of the machinery that ensures genome stability.
 * Acetylation of H3 lysine 56 (H3K56Ac): H3K56Acx is required for genome stability. H3K56 is acetylated by the p300/Rtt109 complex,   but is rapidly deacetylated around sites of DNA damage. H3K56 acetylation is also required to stabilise stalled replication forks, preventing dangerous replication fork collapses.  Although in general mammals make far greater use of histone modifications than microorganisms, a major role of H3K56Ac in DNA replication exists only in fungi, and this has become a target for antibiotic development.
 * Trimethylation of H3 lysine 36 (H3K36me3)
 * H3K36me3 has the ability to recruit the MSH2-MSH6 (hMutSα) complex of the DNA mismatch repair pathway. Consistently, regions of the human genome with high levels of H3K36me3 accumulate less somatic mutations due to mismatch repair activity.

Chromosome condensation

 * Phosphorylation of H3 at serine 10 (phospho-H3S10): The mitotic kinase aurora B phosphorylates histone H3 at serine 10, triggering a cascade of changes that mediate mitotic chromosome condensation. Condensed chromosomes therefore stain very strongly for this mark, but H3S10 phosphorylation is also present at certain chromosome sites outside mitosis, for example in pericentric heterochromatin of cells during G2. H3S10 phosphorylation has also been linked to DNA damage caused by R-loop formation at highly transcribed sites.

 * Phosphorylation H2B at serine 10/14 (phospho-H2BS10/14): Phosphorylation of H2B at serine 10 (yeast) or serine 14 (mammals) is also linked to chromatin condensation, but for the very different purpose of mediating chromosome condensation during apoptosis.  This mark is not simply a late acting bystander in apoptosis as yeast carrying mutations of this residue are resistant to hydrogen peroxide-induced apoptotic cell death.

Addiction
Epigenetic modifications of histone tails in specific regions of the brain are of central importance in addictions. Once particular epigenetic alterations occur, they appear to be long lasting "molecular scars" that may account for the persistence of addictions.

Cigarette smokers (about 15% of the US population) are usually addicted to nicotine. After 7 days of nicotine treatment of mice, acetylation of both histone H3 and histone H4 was increased at the FosB promoter in the nucleus accumbens of the brain, causing 61% increase in FosB expression. This would also increase expression of the splice variant Delta FosB. In the nucleus accumbens of the brain, Delta FosB functions as a "sustained molecular switch" and "master control protein" in the development of an addiction.

About 7% of the US population is addicted to alcohol. In rats exposed to alcohol for up to 5 days, there was an increase in histone 3 lysine 9 acetylation in the pronociceptin promoter in the brain amygdala complex. This acetylation is an activating mark for pronociceptin. The nociceptin/nociceptin opioid receptor system is involved in the reinforcing or conditioning effects of alcohol.

Methamphetamine addiction occurs in about 0.2% of the US population. Chronic methamphetamine use causes methylation of the lysine in position 4 of histone 3 located at the promoters of the c-fos and the C-C chemokine receptor 2 (ccr2) genes, activating those genes in the nucleus accumbens (NAc). c-fos is well known to be important in addiction. The ccr2 gene is also important in addiction, since mutational inactivation of this gene impairs addiction.

Synthesis
The first step of chromatin structure duplication is the synthesis of histone proteins: H1, H2A, H2B, H3, H4. These proteins are synthesized during S phase of the cell cycle. There are different mechanisms which contribute to the increase of histone synthesis.

Yeast
Yeast carry one or two copies of each histone gene, which are not clustered but rather scattered throughout chromosomes. Histone gene transcription is controlled by multiple gene regulatory proteins such as transcription factors which bind to histone promoter regions. In budding yeast, the candidate gene for activation of histone gene expression is SBF. SBF is a transcription factor that is activated in late G1 phase, when it dissociates from its repressor Whi5. This occurs when Whi5 is phosphorylated by Cdc8 which is a G1/S Cdk. Suppression of histone gene expression outside of S phases is dependent on Hir proteins which form inactive chromatin structure at the locus of histone genes, causing transcriptional activators to be blocked.

Metazoan
In metazoans the increase in the rate of histone synthesis is due to the increase in processing of pre-mRNA to its mature form as well as decrease in mRNA degradation; this results in an increase of active mRNA for translation of histone proteins. The mechanism for mRNA activation has been found to be the removal of a segment of the 3' end of the mRNA strand, and is dependent on association with stem-loop binding protein (SLBP). SLBP also stabilizes histone mRNAs during S phase by blocking degradation by the 3'hExo nuclease. SLBP levels are controlled by cell-cycle proteins, causing SLBP to accumulate as cells enter S phase and degrade as cells leave S phase. SLBP are marked for degradation by phosphorylation at two threonine residues by cyclin dependent kinases, possibly cyclin A/ cdk2, at the end of S phase. Metazoans also have multiple copies of histone genes clustered on chromosomes which are localized in structures called Cajal bodies as determined by genome-wide chromosome conformation capture analysis (4C-Seq).

Link between cell-cycle control and synthesis
Nuclear protein Ataxia-Telangiectasia (NPAT), also known as nuclear protein coactivator of histone transcription, is a transcription factor which activates histone gene transcription on chromosomes 1 and 6 of human cells. NPAT is also a substrate of cyclin E-Cdk2, which is required for the transition between G1 phase and S phase. NPAT activates histone gene expression only after it has been phosphorylated by the G1/S-Cdk cyclin E-Cdk2 in early S phase. This shows an important regulatory link between cell-cycle control and histone synthesis.

History
Histones were discovered in 1884 by Albrecht Kossel. The word "histone" dates from the late 19th century and is derived from the German word "Histon", a word itself of uncertain origin, perhaps from Ancient Greek ἵστημι (hístēmi, “make stand”) or ἱστός (histós, “loom”).

In the early 1960s, before the types of histones were known and before histones were known to be highly conserved across taxonomically diverse organisms, James F. Bonner and his collaborators began a study of these proteins that were known to be tightly associated with the DNA in the nucleus of higher organisms. Bonner and his postdoctoral fellow Ru Chih C. Huang showed that isolated chromatin would not support RNA transcription in the test tube, but if the histones were extracted from the chromatin, RNA could be transcribed from the remaining DNA. Their paper became a citation classic. Paul T'so and James Bonner had called together a World Congress on Histone Chemistry and Biology in 1964, in which it became clear that there was no consensus on the number of kinds of histone and that no one knew how they would compare when isolated from different organisms. Bonner and his collaborators then developed methods to separate each type of histone, purified individual histones, compared amino acid compositions in the same histone from different organisms, and compared amino acid sequences  of the same histone from different organisms in collaboration with Emil Smith from UCLA. For example, they found Histone IV sequence to be highly conserved between peas and calf thymus. However, their work on the biochemical characteristics of individual histones did not reveal how the histones interacted with each other or with DNA to which they were tightly bound.

Also in the 1960s, Vincent Allfrey and Alfred Mirsky had suggested, based on their analyses of histones, that acetylation and methylation of histones could provide a transcriptional control mechanism, but did not have available the kind of detailed analysis that later investigators were able to conduct to show how such regulation could be gene-specific. Until the early 1990s, histones were dismissed by most as inert packing material for eukaryotic nuclear DNA, a view based in part on the models of Mark Ptashne and others, who believed that transcription was activated by protein-DNA and protein-protein interactions on largely naked DNA templates, as is the case in bacteria.

During the 1980s, Yahli Lorch and Roger Kornberg showed that a nucleosome on a core promoter prevents the initiation of transcription in vitro, and Michael Grunstein demonstrated that histones repress transcription in vivo, leading to the idea of the nucleosome as a general gene repressor. Relief from repression is believed to involve both histone modification and the action of chromatin-remodeling complexes. Vincent Allfrey and Alfred Mirsky had earlier proposed a role of histone modification in transcriptional activation, regarded as a molecular manifestation of epigenetics. Michael Grunstein and David Allis found support for this proposal, in the importance of histone acetylation for transcription in yeast and the activity of the transcriptional activator Gcn5 as a histone acetyltransferase.

The discovery of the H5 histone appears to date back to the 1970s, and it is now considered an isoform of Histone H1.

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

title: Histone


text:
Talk:Hierarchical relationship

Hi Seb,

Re this
 * Generalizations: asymmetrical relationship
 * Specializations: None yet
 * Involved in: Hierarchy
 * Primary Domain: Interdisciplinarity
 * Other Potential Examples:

I really wonder what use this sort of thing has in an encyclopedia. I don't think it helps particularly. I mean no offense, but my considered opinion is that we should stick with prose English sentences. So, instead of writing "Generalizations: asymmetrical relationship" we should write, "Hierarchical relationships are asymmetrical relationships." And if we do have the latter sort of sentence in the article, adding the above sort of guide creates more confusion than enlightenment. I do not at all mean to cast aspersions on the project of creating a conceptual hierarchy a la WikiProject Concepts. But I am increasingly of the opinion that you should pursue it on a different wiki. I am sure that Jimbo Wales would be delighted to set up a wiki for the project on Wikicities.com. Will you please consider that? --LMS

I think of the list as a helpful navigational complement appended to the article. I have to quote you from WikiProject Concepts/Recap2: "Wikipedia is also a completely open project that has thrived because people have felt free to contribute their knowledge in whatever format they felt comfortable [...] making participants feel comfortable contributing their knowledge is of overriding importance." This is the form in which I feel most comfortable to contribute my knowledge. But you (and everyone) are free to edit it, turn it into prose or scrap it altogether. --Seb

I stand by that remark of mine, and it is very relevant here; you're right to bring it up. That sentiment is why I didn't just scrap it without consulting you first. Doing so would, I imagine, alienate you from the project, which I want to avoid.

The list--or something like it--does have considerable inherent interest, in the same way that "ontology" as practiced by computer scientists has considerable inherent interest (for you and I at least). That said, my opinion is that the list isn't particularly useful as a navigational complement. The names you give for conceptual relations--generalizations, specializations, involved in, primary domain, and other examples--do not call any clear concepts to my mind. There's a variety of things you could mean by any of those terms. That in itself doesn't mean the list is useless; it does mean that you would have to expect users to learn your theory about how concepts are interrelated, or at least this jargon. Moreover, many thinking people would disagree with the theory, because that's just how people are (not necessarily because there's anything wrong with your theory). Consequently, what you might want people to regard as navigational links would very likely, in my opinion, be regarded as the application of your own idiosyncratic theory about how concepts are interrelated to otherwise unbiased articles.

If, by contrast with all that, you were simply to add to the body of the article all of the information that you are trying to convey in your list of links, rendered instead in full prose English sentences, then probably no one would have grounds for complaint. Anyone who is adequately familiar with the subject matter would be able to assess whether the sentences are true or not and whether they shed light on the topic (as I am sure they do), and anyone who is competent enough to learn from what you've written will understand what you intended originally to convey by the list of links.

Feel free to disagree, of course. It's possible that my analysis is off somehow. --LMS

I think this page should go -- its content just seems to be made up a priori. And is "hierarchial relationship" significant enough for an article? Sure, if there is some research on this topic, mention it. But it mostly seems to be just an attempt to create an abstract a priori categorisation of the universe. Contemporary encyclopedias don't try to be an abstract categorisation of the everything that is, although some medieveal or ancient (or even early modern) ones did. I therefore propose deleting this page, unless there are major objections. -- SJK

title: Talk:Hierarchical relationship


text:
Hierarchical organization

A hierarchical organization or hierarchical organisation (see spelling differences) is an organizational structure where every entity in the organization, except one, is subordinate to a single other entity. This arrangement is a form of hierarchy. In an organization, this hierarchy usually consists of a singular/group of power at the top with subsequent levels of power beneath them. This is the dominant mode of organization among large organizations; most corporations, governments, criminal enterprises, and organized religions are hierarchical organizations with different levels of management power or authority. For example, the broad, top-level overview of the hierarchy of the Catholic Church consists of the Pope, then the Cardinals, then the Archbishops, and so on. Another example is the hierarchy between the four castes in the Hindu caste system, which arises from the religious belief "that each is derived from a different part of the creator God’s (Brahma) body, descending from the head downwards.”

Members of hierarchical organizational structures mainly communicate with their immediate superior and their immediate subordinates. Structuring organizations in this way is useful, partly because it reduces the communication overhead costs by limiting information flows.

Visualization
A hierarchy is typically visualized as a pyramid, where the height of the ranking or person depicts their power status and the width of that level represents how many people or business divisions are at that level relative to the whole—the highest-ranking people are at the apex, and there are very few of them, and in many cases only one; the base may include thousands of people who have no subordinates. These hierarchies are typically depicted with a tree or triangle diagram, creating an organizational chart or organogram. Those nearest the top have more power than those nearest the bottom, and there being fewer people at the top than at the bottom. As a result, superiors in a hierarchy generally have higher status and obtain higher salaries and other rewards than their subordinates.

Although the image of organizational hierarchy as a pyramid is widely used, strictly speaking such a pyramid (or organizational chart as its representation] draws on two mechanisms: hierarchy and division of labour. As such, a hierarchy can, for example, also entail a boss with a single employee. When such a simple hierarchy grows by subordinates specialising (e.g. in production, sales, and accounting) and subsequently also establishing and supervising their own (e.g. production, sales, accounting) departments, the typical pyramid arises. This specialisation process is called division of labour.

Common social manifestations
Governmental organizations and most companies feature similar hierarchical structures. Traditionally, the monarch stood at the pinnacle of the state. In many countries, feudalism and manorialism provided a formal social structure that established hierarchical links pervading every level of society, with the monarch at the top.

In modern post-feudal states the nominal top of the hierarchy still remains a head of state – sometimes a president or a constitutional monarch, although in many modern states the powers of the head of state are delegated among different bodies. Below or alongside this head there is commonly a senate, parliament or congress; such bodies in turn often delegate the day-to-day running of the country to a prime minister, who may head a cabinet. In many democracies, constitutions theoretically regard "the people" as the notional top of the hierarchy, above the head of state; in reality, the people's influence is often restricted to voting in elections or referendums.

In business, the business owner traditionally occupies the pinnacle of the organization. Most modern large companies lack a single dominant shareholder and for most purposes delegate the collective power of the business owners to a board of directors, which in turn delegates the day-to-day running of the company to a managing director or CEO. Again, although the shareholders of the company nominally rank at the top of the hierarchy, in reality many companies are run at least in part as personal fiefdoms by their management. Corporate governance rules attempt to mitigate this tendency.

Origins and development of social hierarchical organization
Smaller and more informal social units – families,  bands, tribes, special interest groups – which may form spontaneously, have little need for complex hierarchies – or indeed for any hierarchies. They may rely on self-organizing tendencies. A conventional view ascribes the growth of hierarchical social habits and structures to increased complexity; the religious syncretism and issues of tax-gathering in expanding empires played a role here.

However, others have observed that simple forms of hierarchical leadership naturally emerge from interactions in both human and non-human primate communities. For instance, this occurs when a few individuals obtain more status in their tribe, (extended) family or clan, or when competences and resources are unequally distributed across individuals.

Studies
The organizational development theorist Elliott Jaques identified a special role for hierarchy in his concept of requisite organization. The iron law of oligarchy, introduced by Robert Michels, describes the inevitable tendency of hierarchical organizations to become oligarchic in their decision making.

The Peter Principle is a term coined by Laurence J. Peter in which the selection of a candidate for a position in an hierarchical organization is based on the candidate's performance in their current role, rather than on abilities relevant to the intended role. Thus, employees only stop being promoted once they can no longer perform effectively, and managers in an hierarchical organization "rise to the level of their incompetence."

Hierarchiology is another term coined by Laurence J. Peter, described in his humorous book of the same name, to refer to the study of hierarchical organizations and the behavior of their members.

"Having formulated the Principle, I discovered that I had inadvertently founded a new science, hierarchiology, the study of hierarchies. The term hierarchy was originally used to describe the system of church government by priests graded into ranks. The contemporary meaning includes any organization whose members or employees are arranged in order of rank, grade or class. Hierarchiology, although a relatively recent discipline, appears to have great applicability to the fields of public and private administration."

David Andrews' book The IRG Solution: Hierarchical Incompetence and how to Overcome it argued that hierarchies were inherently incompetent, and were only able to function due to large amounts of informal lateral communication fostered by private informal networks.

Types of hierarchy
Hierarchical organization is a phenomenon with many faces. To understand and map this diversity, various typologies have been developed. Formal versus informal hierarchy is a well-known typology, but one can also distinguish four hierarchy types.

Two types of hierarchy: Formal and informal
A well-known distinction is between formal and informal hierarchy in organizational settings. According to Max Weber, the formal hierarchy is the vertical sequence of official positions within one explicit organizational structure, whereby each position or office is under the control and supervision of a higher one. The formal hierarchy can thus be defined as “an official system of unequal person-independent roles and positions which are linked via lines of top-down command-and-control.” By contrast, an informal hierarchy can be defined as person-dependent social relationships of dominance and subordination, emerging from social interaction and becoming persistent over time through repeated social processes. The informal hierarchy between two or more people can be based on difference in, for example, seniority, experience or social status. The formal and informal hierarchy may complement each other in any specific organization and therefore tend to co-exist in any organization. But the general pattern observed in many organizations is that when the formal hierarchy decreases (over time), the informal hierarchy increases, or vice versa.

Four types of hierarchy
A more elaborate typology of hierarchy in social systems entails four types: hierarchy as a ladder of formal authority, ladder of achieved status, self-organized ladder of responsibility, and an ideology-based ladder. The first two types can be equated with the formal and informal hierarchy, as previously defined. Accordingly, this typology extends the formal and informal hierarchy with two other types.

Hierarchy as ladder of formal authority
This type of hierarchy is defined as a sequence of levels of formal authority, that is, the authority to make decisions. This results in a ladder that systematically differentiates the authority to make decisions. A typical authority-based hierarchy in companies is: the board of directors, CEO, departmental managers, team leaders, and other employees. The authority-based hierarchy, also known as the formal hierarchy, to a large extent arises from the legal structure of the organization: for example, the owner of the firm is also the CEO or appoints the CEO, who in turn appoints and supervises departmental managers, and so forth.

Hierarchy as ladder of achieved status
Also known as the informal hierarchy (defined earlier), this type of hierarchy draws on unofficial mechanisms for ranking people. It involves differences in status, other than those arising from formal authority. Status is one’s social standing or professional position, relative to those of others. In anthropology and sociology, this notion of status is also known as achieved status, the social position that is earned instead of being ascribed. The underlying mechanism is social stratification, which draws on shared cultural beliefs (e.g. regarding expertise and seniority as drivers of status) that can make status differences between people appear natural and fair. A ladder of achieved status is socially constructed, which makes it fundamentally different from the ladder of authority that (largely) arises from an underlying legal structure. The social-constructivist nature of status also implies that ladders of achieved status especially arise in groups of people that frequently interact—for example, a work unit, team, family, or neighbourhood.

Hierarchy as self-organized ladder of responsibility
In the literature on organization design and agility, hierarchy is conceived as a requisite structure that emerges in a self-organized manner from operational activities. For example, a small firm composed of only three equivalent partners can initially operate without any hierarchy; but substantial growth in terms of people and their tasks will create the need for coordination and related managerial activities; this implies, for example, that one of the partners starts doing these coordination activities. Another example involves organizations adopting holacracy or sociocracy, with people at all levels self-organizing their responsibilities;  that is, they exercise “real” rather than formal authority. In this respect, responsibility is an expression of self-restraint and intrinsic obligation. Examples of self-organized ladders of responsibility have also been observed in (the early stages of) worker cooperatives, like Mondragon, in which hierarchy is created in a bottom-up manner.

Hierarchy as ladder of ideology
In a hierarchy driven by ideology, people establish themselves as legitimate leaders by invoking some (e.g., religious, spiritual or political) idea to justify the hierarchical relationship between higher and lower levels. Ideological hierarchies have a long history, for example in the administrative hierarchies headed by pharaohs in ancient Egypt or those headed by kings in medieval Europe. The main legitimacy of any pharaoh or king arose from the strong belief in the idea that the pharaoh/king acts as the intermediary between the gods and the people, and thus deputizes for the gods. Another example is the hierarchy prevailing until today in the Balinese community, which is strongly connected to the rice cycle that is believed to constitute a hierarchical relationship between gods and humans, both of whom must play their parts to secure a good crop; the same ideology also legitimizes the hierarchical relationship between high and low castes in Bali. Ideological ladders have also long sustained the way the Catholic church and the Hindu caste system operates. Hierarchies of ideology also exist in many other settings, for instance, those driven by prevailing values and beliefs about how the (e.g. business) world should operate. An example is the ideology of “maximizing shareholder value”, which is widely used in publicly traded companies. This ideology helps in creating and sustaining the image of a clear hierarchy from shareholders to employees—although, in practice, the separation of legal ownership and actual control implies that the CEO together with the Board of Directors are at the top of the corporate hierarchy. Given that public corporations (primarily) thrive on ladders of authority; this example also demonstrates how ladders of authority and ideology can complement and reinforce each other.

Criticism and alternatives
The work of diverse theorists such as William James (1842–1910), Michel Foucault (1926–1984) and Hayden White (1928-2018) makes important critiques of hierarchical epistemology. James famously asserts in his work on radical empiricism that clear distinctions of type and category are a constant but unwritten goal of scientific reasoning, so that when they are discovered, success is declared. But if aspects of the world are organized differently, involving inherent and intractable ambiguities, then scientific questions are often considered unresolved. A hesitation to declare success upon the discovery of ambiguities leaves heterarchy at an artificial and subjective disadvantage in the scope of human knowledge. This bias is an artifact of an aesthetic or pedagogical preference for hierarchy, and not necessarily an expression of objective observation.

Hierarchies and hierarchical thinking have been criticized by many people, including Susan McClary (born 1946), and by one political philosophy which vehemently opposes hierarchical organization: anarchism. Heterarchy, the most commonly proposed alternative to hierarchy, has been combined with responsible autonomy by Gerard Fairtlough in his work on triarchy theory. The most beneficial aspect of a hierarchical organization is the clear command-structure that it establishes. However, hierarchy may become dismantled by abuse of power.

Matrix organizations became a trend (or management fad) in the second half of the 20th century.

Amidst constant innovation in information and communication technologies, hierarchical authority structures are giving way to greater decision-making latitude for individuals and more flexible definitions of job activities; and this new style of work presents a challenge to existing organizational forms, with some research studies contrasting traditional organizational forms with groups that operate as  online communities that are characterized by personal motivation and the satisfaction of making one's own decisions. When all levels of a hierarchical organization have access to information and communication via digital means, power structures may align more as a wirearchy, enabling the flow of power and authority to be based not on hierarchical levels, but on information, trust, credibility, and a focus on results.

title: Hierarchical organization


text:
Talk:Hierarchical organization

Opening heading
This is interesting, but it ignores the long history of the term 'hierarchy' in favor of contemporary business. 'Boss'? Not even a sense of context for that word? --MichaelTinkle

"Hierarchial organization, as a concept, is opposed by just one political ideology, namely anarchism." -- I don't believe this: anarchism is usually defined as opposition to the concept of government, not hierarchical organisations in general. -- "Libertarian socialists see themselves as dedicated to opposing all forms of authority, coercion and social hierarchy. In this they include not only coercion by the state, but also by businesses, schools, religous institutions and at times even the family as well." - - from wikipedia on Libertarian socialism, which is the oldest, most widespread, form of anarchism. You must be refering to Anarcho-capitalism.

Requested move

 * The following discussion is an archived discussion of a requested move. Please do not modify it. Subsequent comments should be made in a new section on the talk page. No further edits should be made to this section.

The result of the move request was: No consensus, page not moved  Ron h jones (Talk) 23:28, 27 June 2010 (UTC)

Organizational hierarchy → — Common name, and less confusing: this article is about a kind of organizational structure, not a variety of hierarchy. Relisted.   A rbitrarily 0   ( talk ) 23:04, 14 June 2010 (UTC) Pnm (talk) 01:04, 3 June 2010 (UTC)
 * Comment: The reverse move was done in 2009 to avoid confusion with Hierarchy. Now it's causing confusion with Organizational structure instead. A Not to be confused with hatnote directing to hierarchy is a better alternative. --Pnm (talk) 01:04, 3 June 2010 (UTC)
 * Comment: Found the discussion from that move: Talk:Hierarchy --Pnm (talk) 01:16, 3 June 2010 (UTC)
 * The above discussion is preserved as an archive of a requested move. Please do not modify it. Subsequent comments should be made in a new section on this talk page. No further edits should be made to this section.

Relist requested move

 * The following discussion is an archived discussion of a requested move. Please do not modify it. Subsequent comments should be made in a new section on the talk page. No further edits should be made to this section.

The result of the move request was: page moved per request. - GTBacchus(talk) 06:20, 1 January 2011 (UTC)

Organizational hierarchy → Hierarchical organization — A hierarchical organization is an organizational structure, where every entity, except one, is subordinate to a single other entity. The old title is a synonym for organizational structure, which is confusing. --Pnm (talk) 23:50, 27 November 2010 (UTC)
 * Comment: I think I might be able to articulate this more clearly.
 * The most common context for this topic is organizational design. In this context, this type of organization is called a hierarchical organization, meanwhile, organizational hierarchy is synonymous with organizational structure.
 * In a more obscure context like systems theory, I could see how organizational hierarchy might be a better name, to contrast it with other kinds of hierarchy.
 * The article should be named based on its common name in its most common context. --Pnm (talk) 22:17, 31 December 2010 (UTC)
 * The above discussion is preserved as an archive of a requested move. Please do not modify it. Subsequent comments should be made in a new section on this talk page. No further edits should be made to this section.

title: Talk:Hierarchical organization


text:
Harry Secombe

Sir Harry Donald Secombe (8 September 1921 – 11 April 2001) was a Welsh actor, comedian, singer and television presenter. Secombe was a member of the British radio comedy programme The Goon Show (1951–1960), playing many characters, most notably Neddie Seagoon. An accomplished tenor, he also appeared in musicals and films – notably as Mr Bumble in Oliver! (1968) – and, in his later years, was a presenter of television shows incorporating hymns and other devotional songs.

Early life
Secombe was born in St Thomas, Swansea, the third of four children of Nellie Jane Gladys (née Davies), a shop manageress, and Frederick Ernest Secombe, a commercial traveller and office worker for a Swansea wholesale grocery business. From the age of 11 he attended Dynevor School, a state grammar school in central Swansea.

His family were regular churchgoers, belonging to the congregation of St Thomas Church. A member of the choir, from the age of 12 Secombe would perform a sketch entitled The Welsh Courtship at church socials, acting as "feed" to his sister Carol. His elder brother, Fred Secombe, became the author of several books about his experiences as an Anglican priest and rector.

Army service
After leaving school in 1937, Secombe became a pay clerk at Baldwin's store. With war looming, he decided in 1938 that he would join the Territorial Army. Very short sighted, he got a friend to tell him the sight test, and then learnt it by heart. He served as a Lance Bombardier in No.132 Field Regiment of the Royal Artillery. He referred to the unit in which he served during the Second World War in the North African Campaign, Sicily, and Italy, as "The Five-Mile Snipers". While in North Africa Secombe met Spike Milligan for the first time. In Sicily he joined a concert party and developed his own comedy routines to entertain the troops.

When Secombe visited the Falkland Islands to entertain the troops after the 1982 Falklands War, his old regiment promoted him to the rank of sergeant – 37 years after he had been demobbed.

As an entertainer
He made his first radio broadcast in May 1944 on a variety show aimed at the military services. Following the end of fighting in the war but prior to demobilisation, Secombe joined a pool of entertainers in Naples and formed a comedy duo with Spike Milligan.

Secombe joined the cast of the Windmill Theatre in 1946, using a routine he had developed in Italy about how people shaved. An early review said that Secombe was "an original humorist of the infectious type and is very funny in a series showing how different men shave and in an impression of a vocalist." Secombe always claimed that his ability to sing could always be counted on to save him when he bombed.

After a regional touring career, his first break came in radio in 1951 when he was chosen as resident comedian for the Welsh series Welsh Rarebit, followed by appearances on Variety Bandbox and a regular role in Educating Archie.

Secombe met Michael Bentine at the Windmill Theatre, and he was introduced to Peter Sellers by his agent Jimmy Grafton. Together with Spike Milligan, the four wrote a comedy radio script, and Those Crazy People was commissioned and first broadcast on 28 May 1951. Produced by Dennis Main Wilson, this soon became The Goon Show and the show remained on the air until 1960. Secombe mainly played Neddie Seagoon, around whom the show's absurd plots developed. In 1955, whilst appearing on The Goon Show, Secombe was approached by the BBC to step in at short notice to take the lead in the radio comedy Hancock's Half Hour. The star of the show, Tony Hancock, had decided to take an unannounced break abroad, on the day before the live airing of the second season. Secombe appeared in the lead for the first three episodes and had a guest role in the fourth after Hancock's return. All four episodes are lost, but following the discovery of the original scripts, the episodes were rerecorded in 2017, with his son, Andrew Secombe performing the role held by his late father.

With the success of The Goon Show, Secombe developed a dual career as both a comedy actor and a singer. At the beginning of his career as an entertainer, his act would end with a joke version of the duet Sweethearts, in which he sang both the baritone and falsetto parts. Trained under Italian maestro Manlio di Veroli, he emerged as a bel canto tenor (characteristically, he insisted that in his case this meant "can belto") and had a long list of best-selling record albums to his credit.

In 1958 he appeared in the film Jet Storm, which starred Dame Sybil Thorndike and Richard Attenborough and in the same year Secombe starred in the title role in Davy, one of Ealing Studios' last films.

The power of his voice allowed Secombe to appear in many stage musicals. This included 1963's Pickwick, based on Charles Dickens's The Pickwick Papers, which gave him the no. 18 hit single "If I Ruled the World" – his later signature tune. In 1965 the show was produced on tour in the United States, where, on Broadway, he garnered a nomination for a Tony Award for Best Actor in a Musical. Secombe scored his biggest hit single in 1967 with his version of "This Is My Song", which peaked at no. 2 on the charts in March 1967 while a recording by Petula Clark, which had hit no. 1 in February, was still in the top ten. He also appeared in the musical The Four Musketeers (1967) at Drury Lane, as Mr. Bumble in Carol Reed's film of Oliver! (1968), and in the Envy segment of The Magnificent Seven Deadly Sins (1971).

He went on to star in his own television show, The Harry Secombe Show, which debuted on Christmas Day 1968 on BBC1 and ran for 31 episodes until 1973. A sketch comedy show featuring Julian Orchard as Secombe's regular sidekick, the series also featured guest appearances by fellow Goon Spike Milligan as well as leading performers such as Ronnie Barker and Arthur Lowe. Secombe later starred in similar vehicles such as Sing a Song of Secombe and ITV's Secombe with Music during the 1970s.

Later career
Later in life, Secombe (whose brother Fred Secombe was a priest in the Church in Wales, part of the Anglican Communion) attracted new audiences as a presenter of religious programmes, such as the BBC's Songs of Praise and ITV's Stars on Sunday and Highway. He was also a special programming consultant to Harlech Television and hosted a Thames Television programme in 1979 entitled Cross on the Donkey's Back. In the latter half of the 1980s, Secombe personally sponsored a football team for boys aged 9–11 in the local West Sutton Little League, 'Secombes Knights'.

In 1990, he was one of a few to be honoured by a second appearance on This Is Your Life, when he was surprised by Michael Aspel at a book signing in a London branch of WH Smith. Secombe had been a subject of the show previously in March 1958 when Eamonn Andrews surprised him at the BBC Television Theatre.

Honours
In 1963 he was appointed a Commander of the Order of the British Empire (CBE).

He was knighted in 1981, and jokingly referred to himself as Sir Cumference (in recognition of his rotund figure). The motto he chose for his coat of arms was "GO ON", a reference to goon.

Later life and death
Secombe had peritonitis in 1980. Within two years, taking advice from doctors, he had lost five stone in weight. He had a stroke in 1997 and his colon burst, from which he made a slow recovery. He was then diagnosed with prostate cancer in September 1998. Following a second stroke in 1999, he was forced to abandon his television career, but made a documentary about his condition in the hope of giving encouragement to others with the condition. Secombe had diabetes in the latter part of his life.

Secombe died on 11 April 2001 at the age of 79, from prostate cancer, in hospital in Guildford, Surrey. His ashes are interred at the parish church of Shamley Green, and a later memorial service to celebrate his life was held at Westminster Abbey on 26 October 2001. As well as family members and friends, the service was attended by Charles, Prince of Wales and representatives of Prince Philip, Duke of Edinburgh, Anne, Princess Royal, Princess Margaret, Countess of Snowdon and Prince Edward, Duke of Kent. On his tombstone is the inscription: "To know him was to love him."

At Peter Sellers's funeral in 1980, Secombe sang a hymn and Spike Milligan joked: "I hope you die before me because I don't want you singing at my funeral." After Milligan's death in 2002, a recording of Secombe singing Guide me, O Thou great Redeemer was played at Milligan's memorial service.

The Secombe Theatre in Sutton, Greater London, was named after him. He is also fondly remembered at the London Welsh Centre, where he opened the bar on St Patrick's Day (17 March) 1971.

Family
Secombe met Myra Joan Atherton at the Mumbles Dance Hall in 1946. The couple were married from 1948 until his death, and had four children:
 * Jennifer Secombe (died 2019), widow of actor Alex Giannini. She was her father's agent in his later years.
 * Andy Secombe, a voice actor, film actor and author
 * David Secombe, a writer and photographer
 * Katy Secombe, an actress

Myra, Lady Secombe died on 7 February 2018, aged 93.

Singles

 * "On with the Motley" (Vesti la giubba) (1955) UK #6
 * "Bless This House"
 * "If I Ruled the World" (1963) UK #18
 * "This Is My Song" (1967) UK #2

Albums

 * Sacred Songs (1962) UK #16
 * Pickwick (Original Cast Album) (1965)
 * Secombe's Personal Choice (1967) UK #6
 * If I Ruled the World (1971) UK #17
 * The Magnificent Voice of Harry Secombe (1972) AUS #14
 * With a Song In My Heart (1977) AUS #24
 * Captain Beaky and His Band (1977)
 * Bless This House: 20 Songs of Joy (1978) UK #8, AUS #28
 * This Is My Song (1983) AUS #9
 * All Things Bring and Beautiful (1983) AUS #31
 * Songs for Everyone (1986) AUS #43
 * Highway of Life (1986) UK #45
 * Count Your Blessings (1988) AUS #93
 * Your Sincerely (1991) UK #46

Fiction

 * Twice Brightly (1974) Robson Books ISBN 0903895234
 * Welsh Fargo (1981) Robson Books ISBN 0903895870

Children's

 *  Katy and the Nurgla (1980) ISBN 0140311890

Autobiographical

 * Goon for Lunch (1975) M. J. Hobbs ISBN 0718112830
 * Goon Abroad (1982) Robson Books ISBN 0860511936
 * Arias and Raspberries (1989) Robson Books ISBN 0860516245
 * Strawberries and Cheam (1998) Robson Books ISBN 1861050488
 * Alternative ISBNs for 2004 publication: ISBN 978-1-86105-811-9; ISBN 1-86105-811-X (paperback).

title: Harry Secombe