What's the relationship between priming and availability heuristic? As I have understood, availability heuristic means that things that are "available" in one's cognition (one has thought recently) are prone to influence one's perception.

Priming has been explained as that the word 'doctor' is recognized more frequently than 'bread' after a word 'nurse'.

I find that in this sense priming would be a subcategory of availability or vice versa. ('doctor' is recognized more frequently when 'nurse' is available in one's cognition)

Why did Amos Tversky and Daniel Kahneman introduce availability instead of sticking with priming? 


Tversky, A., &amp; Kahneman, D. (1974). Judgment under uncertainty: Heuristics and biases. science, 185(4157), 1124-1131.
Psychological Priming and Availability Heuritic are both concepts within Social Psychology and Behavioural Psychology.  Although I can see where you are trying to make a link here, and there could be times where both are at play, Psychological Priming is different to Availability Heuristic.

Psychological Priming


  Priming is a nonconscious form of human memory concerned with perceptual identification of words and objects. It refers to activating particular representations or associations in memory just before carrying out an action or task. For example, a person who sees the word "yellow" will be slightly faster to recognize the word "banana." This happens because yellow and banana are closely associated in memory. Additionally, priming can also refer to a technique in psychology used to train a person's memory in both positive and negative ways.(Psychology Today, n.d.)


Doing some research on the history, the idea first took hold in 1932 with a book called Remembering: A Study in Experimental and Social Psychology (Bartlett, 1932) and the first demonstration of Priming was in 1971 within experiments by E. F. Loftus, J. F. Juola and R. C. Atkinson's (Colins &amp; Loftus, 1975) [See also - The History of Priming (Vogel, 2014)]

A couple of other good examples of Psychological Priming, different to the yellow banana above, was provided in an article by Jesse Marczyk Ph.D. in Psychology Today (Marczyk, 2013)

Priming can affect perceptions about the world


  [H]olding a warm drink (instead of a cold one) can lead you judge other people as more caring and generous; a finding that falls under the umbrella of embodied cognition. Why would such a finding arise? If I understand correctly, the line of thought is that holding a warm drink activates some part of your brain that holds the concept "warm;" as that concept is tied indirectly to personality (e.g., "He's a really warm and friendly person"), you end up thinking the person is nicer than you otherwise would. Warm drinks prime the concept of emotional warmth.


[See also: This article in Johnny Holland for more examples]

Priming on a behavioural level instead of a perceptual one


  [R]esearch on stereotype threat suggests that if you remind women of their gender before a math test (in other words, you're priming gender), they will tend to perform worse than women who were not primed because the concept of "woman" is related to stereotypes of "being worse at math."


[See also: Power Poses and Elderly Prime Effects on Walking Speed
]

Availability Heuristic

This is a cognitive bias


  The tendency to overestimate the likelihood of events with greater "availability" in memory, which can be influenced by how recent the memories are or how unusual or emotionally charged they may be


One good example for this can be found in an article by Jamie Madigan Ph.D. in Psychology Today (Madigan, 2013)

In this example, with people who have always lived in areas where their internet connection is reliable, the availability heuristic influences their decision-making, belief, and behavioral bias with regard to internet connection in other areas.


  Orthy's estimation of the number of people who have stable Internet connections and who should thus "#dealwithit" is probably influenced by the availability heuristic. Or rather, the UNavailability heuristic.


Madigan went on to say,


  The availability heuristic is an old mental foible that I've written about before, and the short version is that the easier it is to remember of examples of something, the more prevalent, frequent, or large we think it is. But interestingly, the opposite is also true: will tend to think something is less prevalent or less frequent when it's harder to remember examples of it. Various things make an event or a condition easier to remember, but they often include experiencing it ourselves, having seen it recently, or knowing someone who has.
  
  My favorite example of this (un)availability heuristic is a hack created by University of California Los Angeles professor Craig Fox (2006) to boost his student class evaluations. Before completing the evaluation forms, Fox asked half the students to suggest 2 ways to improve the class (an easy task), then asked the other half to suggest 10 ways to improve it (a much harder task). Those who go quickly got stumped on the road to coming up with 10 improvements gave Fox higher course evaluation ratings than the others. Why? Because they misinterpreted the difficulty of recalling so many flaws as evidence that there were few flaws at all.


References

Bartlett, F. C. (1935). Remembering: A Study in Experimental and Social Psychology Cambridge, UK: Cambridge University Press

Collins, A. M., &amp; Loftus, E. F. (1975). A spreading-activation theory of semantic processing. Psychological Review, 82(6), pp. 407—428.
DOI: 10.1037/0033-295X.82.6.407

Fox, C. (2006). The availability heuristic in the classroom: How soliciting more criticism can boost your course ratings. Judgment and Decision Making, 1(1), pp. 86—90.Free PDF available at:
Society for Judgment and Decision Making and
ResearchGate
Cannot find DOI

Madigan, J. (2013). The Availability Heuristic Is Always On [Online]
Available at: https://www.psychologytoday.com/blog/mind-games/201304/the-availability-heuristic-is-always

Marczyk, J. (2017). The Adaptive Significance of Priming [Online]
Available at: https://www.psychologytoday.com/blog/pop-psych/201701/the-adaptive-significance-priming

Psychology Today (n.d.). Priming [Online]
Available at: https://www.psychologytoday.com/basics/priming

Vogel, R. (2014). The History of Priming [Online]
Available at: https://prezi.com/ep5dwcwbq2dl/the-history-of-priming